數(shù)據(jù)結(jié)構(gòu)與算法 線性表
2022-04-25 23:06:40

//AUB

//La表示A集合，Lb表示B集合
void unionL(List *La,List Lb){
    int La_len ,Lb_len,i;
    ElemType e;
    
    La_len = ListLength(*La);
    Lb_len = ListLength(Lb);
    
    for(i = 1;i<=Lb_len;i++){
        GetElem(Lb,i,&e)
        if(!LocateElem(*La,e)){
            ListInsert(La,++La_len,e);
        }
    }
}

順序存儲(chǔ)結(jié)構(gòu)的結(jié)構(gòu)代碼

#define MAXSIZE 20
typedef int ElemType;
typedef struct{
    ElemType data[MAXSIZE];
    int length;//線性表當(dāng)前長度
} SqList;

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
//Status是函數(shù)的類型，其值是函數(shù)結(jié)果的狀態(tài)碼，入OK等。
//初始條件：順序線性表L已存在，1 <= i <= ListLength(L)
//操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值

Status GetElem(SqList L,int i,ElemType *e){
    if(L.length == 0 || i < 1 || i>L.length){
        return ERROR;
    }
    *e = L.data[i-1];
    return OK;
}

//初始條件：順序線性表L已存在，1<=i<=ListLength(L)
//操作結(jié)果：在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e,L長度+1

Ststus ListInsert(SqList *L,int i;ElemTYpe e){
    int k;
    if(L->length == MAXSIZE){//順序線性表已經(jīng)滿了
        return ERROR;
    }
    if(i<1 || i>L->length){//當(dāng)i不在范圍內(nèi)時(shí)
        return ERROR;
    }
    if(i<= L->length){//若插入元素位置不再表尾
        //要將插入位置后元素向后移動(dòng)一位
        for(k=L->length-1;k>=i-1;k--){
            L->data[k+1] = L->data[k];
        }
    }
    L->data[i-1] = e;//將新元素插入
    L->length++;
    return OK;
}

//初始條件：順序線性表L已存在，1<=i<=ListLength(L)
//操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，并用e返回其值，L的長度-1

Status ListDeleted(SqList *L,int i,ElemType *e){
    int k;
    
    if(L->length == 0){
        return ERROR;
    }
    if(i<1 || i>L->length){
        return ERROR;
    }
    *e = L->data[i-1];

    if(i<L->length){
        for(k=i;k<L->length;k++){
            L->data[k-1] = L->data[k];
        }
    }

    L->length--;
    return OK;
}

優(yōu)點(diǎn)：
1、無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間。
2、可以快速的存取表中的任意位置的元素。

缺點(diǎn)：
1、插入和刪除操作需要移動(dòng)大量元素。
2、當(dāng)線性表長度變化較大時(shí)，難以確定存儲(chǔ)空間的容量。
3、容易造成存儲(chǔ)空間的“碎片”。

頭指針：
頭指針是指鏈表指向第一個(gè)節(jié)點(diǎn)的指針，若鏈表有頭節(jié)點(diǎn)，則是指向頭節(jié)點(diǎn)的指針。
頭指針具有標(biāo)識(shí)作用，所以常用頭指針冠以鏈表的名字（指針變量的名字）。
無論鏈表是否為空，頭指針均不為空。
頭指針是鏈表的必要元素。

頭節(jié)點(diǎn)：
頭節(jié)點(diǎn)是為了操作的統(tǒng)一和方便而設(shè)立的，方在第一個(gè)元素的節(jié)點(diǎn)前，其數(shù)據(jù)域一般無意義（但也可以用來存放鏈表的長度）。
有了頭節(jié)點(diǎn)，對在第一個(gè)元素節(jié)點(diǎn)前插入節(jié)點(diǎn)和刪除第一個(gè)節(jié)點(diǎn)其操作與其他節(jié)點(diǎn)的操作就統(tǒng)一了。
頭節(jié)點(diǎn)不一定是鏈表的必須要素。

typedef struct Node{
    ElemType data;//數(shù)據(jù)域
    struct Node *Next;//指針域
}Node;
typedef struct Node *LinkList;

//初始條件：順序線性表L已存在，1<=i<=ListLength(L)
//操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值

Status GetElem(LinkList L,int i,ElemType *e){
    int j;
    LinkList p;
    
    p = L->next;
    j = 1;

    while(p && j<i){
        p = p->next;
        ++j;
    }

    if(!p || j>i){
        return ERROR;
    }
    *e = p->data;
    return OK;
}

s->next = p->next;
p->next = s;

p->next = s;
s->next = p->next;

//初始條件：鏈表L已經(jīng)存在，1<=i<=ListLength(L)
//操作結(jié)果：在L中第i個(gè)位置前插入新的數(shù)據(jù)元素e，L的長度加1

Status ListInsert(LinkList *L,int i,ElemType e){
    int j;
    LinkList p,s;
    
    p = *L;
    j = 1;

    while(p && j<i){
        p = p->next;
        j++;
    }

    if(!p || j>i){
        return ERROR;
    }

    s = (LinkList)malloc(sizeof(Node));
    s->data = e;

    s->next = p->next;
    p->next = s;

    return OK;
}

p->next = p->next->next;
或
q = p->next;
p->next = q->next;

Status ListDeleted(LinkList *L,int i,ElemType e){
    int j;
    LinkList p,q;
    
    p = *L;
    j = 1;

    while(p && j<i){
        p = p->next;
        j++;
    }

    if(!(p->next) || j>i){
        return ERROR;
    }

    q = p->next;
    p->next = q->next;
    
    *e = q->data;
    free(q);

    return OK;
}

void CreateListHead(LinkList *L,int n){
    LinkList p;
    int i;

    srand(time(0));//初始化隨機(jī)數(shù)字

    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;

    for(i=0;i<n;i++){
        p = (LinkLIst)malloc(sizeof(Node));//生成新節(jié)點(diǎn)
        p->data = rand()%100+1;
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

void CreateListTail(LinkList *L,int n){
    LinkList p,r;
    int i;

    srand(time(0));//初始化隨機(jī)數(shù)字

    *L = (LinkList)malloc(sizeof(Node));
    r = *L;

    for(i=0;i<n;i++){
        p = (LinkLIst)malloc(sizeof(Node));//生成新節(jié)點(diǎn)
        p->data = rand()%100+1;
        r->next = p;
        r = p;//備注：初學(xué)者可能很難理解這句，重點(diǎn)解釋。
    }
    r->next = NULL;
}

Status ClearList(LinkList *L){
    LinkList p,q;

    p = (*L)->next;

    while(p){
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;
    return OK;
}

#define MAXSIZE 1000
typedef struct{
    ElemType data;//數(shù)據(jù)
    int cur;//游標(biāo)
}Component,StaticLinkList[MAXSIZE];

Status InitList(StaticLinkList space){
    int i;
    for(i=0;i<MAXSIZE-1;i++){
        space[i].cur = i+1;
    }
 
    space[MAXSIZE-1].cur = 0;
    return OK;
}

首先是獲得空閑分量的下標(biāo)：
int Malloc_SLL(StaticLinkList space){
    int i = space[0].cur;
    if(space[0].cur){
        space[0].cur = space[i].cur;
        //把它的下一個(gè)分量用來作為備用。
    }
    return i;
}

Status ListInsert(StaticLinkList L ,int i,ElemType e){
    int j,k,l;

    k = MAX_SIZE - 1;//數(shù)組的最后一個(gè)元素

    if(i<1 || i>ListLength(L)+1){
        return ERROR;
    }

    j = Malloc_SLL(L);
    if(j){
        L[j].data = e;
        for(l=1;l<i-1;l++){
            k = L[k].cur;
        }
        L[j].cur = L[k].cur;
        L[k].cur = j;
        return OK;
    }
    return ERROR;
}

void Free_SSL(StaticLinkList space,int k){
    space[k].cur = space[0].cur;
    space[0].cur = k;
}

Status ListDeleted(StaticLinkList L ,int i){
    int j,k;
    
    if(i<1 || j>ListLength(L)){
        return ERROR;
    }

    k = MAX_SIZE-1;

    for(j=1;j<=i-1;j++){
        k = L[k].cur;
    }

    j - L[k].cur;
    L[k].cur = L[j].cur;

    Free_SLL(L,j);
    return OK;
}

單鏈表小結(jié)騰訊面試題

題目：快速找到未知長度單鏈表的中間節(jié)點(diǎn)。

既然是面試題就一定有普通方法和高級方法，而高級方法，而高級方法無疑會(huì)讓面試官大大加分！

普通方法很簡單，首先遍歷一遍單鏈表以確定單鏈表的長度L。然后再次從頭節(jié)點(diǎn)觸發(fā)循環(huán)L/2次找到單鏈表的中間節(jié)點(diǎn)。

算法的復(fù)雜度為：O(L+L/2) = O(3/2L)

能否再優(yōu)化一下這個(gè)時(shí)間復(fù)復(fù)雜度呢？

有一個(gè)很巧妙的方法：利用快慢指針！

利用快慢指針原理：設(shè)置兩個(gè)指針*search、*mid都指向單鏈表的頭節(jié)點(diǎn)。其中*search的移動(dòng)速度是*mid的2倍。當(dāng)*search指向末尾節(jié)點(diǎn)的時(shí)候，*mid正好就在中間了。這也是標(biāo)尺的思想。

GetMidNode.c

Status GetMidNode(LinkList L,ElemType *e){
    LinkList search,mid;
    mid = search = L;

    while(search->next != NULL){
        //search移動(dòng)的速度是mid的2倍
        if(search->next->next !=NULL){
            search = search->next->next;
            mid = mid->next;
        }else{
            search = search->next;
        }
    }
    *e = mid->data;

    return OK;
}

//鏈表存儲(chǔ)結(jié)構(gòu)定義
typedef struct CLinkList{
    int data;
    struct ClinkList *next;
}

void ds_init(node **pNode){
    int item;
    node *temp;
    node *target;

    printf("輸入節(jié)點(diǎn)的值，輸入0完成初始化");

    while(1){
        scanf("%d",&item);
        fflush(stdin);

        if(item == 0){
           return;
        }

        if((*pNode == NULL)){
            //循環(huán)鏈表中只有一個(gè)節(jié)點(diǎn)
            *pNode = (node*)malloc(sizeiof(struct ClinkList));
            if(!(*pNode)){
                exit(0);
            }
            (*pNode)->data = item;
            (*pNode)->next = *pNode;
        }else{
            //找到next指向第一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)
            for(target = (*pNode);target->next!=(*pNode);target = target->next){
                
            }
            //生成一個(gè)新的節(jié)點(diǎn)
            temp = (node *)malloc(sizeof(struct CLinkList));
            if(!temp){
                exit(0);
            }

            temp->data = item;
            temp->next = *pNode;
            target->next = temp;
        }
    }
}

void ds_insert(node **pNode,int i){
    node *temp;
    node *target;
    node *p;
    int item;
    int j;

    printf("輸入要插入節(jié)點(diǎn)的值：");
    scanf("%d",&item);

    if(i == 1){
        //新插入的節(jié)點(diǎn)作為第一個(gè)節(jié)點(diǎn)
        temp = (node *)malloc(sizeof(struct CLinkList));

        if(!temp){
            exit(0);
        }
        temp->data = item;

        //尋找到最后一個(gè)節(jié)點(diǎn)
        for(target = (*pNode);target->next != (*pNode);target = target->next){}
        
        temp->next = (*pNode);
        target->next = temp;
        *pNode = temp;
    }else{
        target = *pNode;

        for(j = 1;j<(i-1);++j){
            target = target->next;
        }
        
        temp = (node *)malloc(sizeof(struct CLinkList));

        if(!temp){
            exit(0);
        }

        temp->data = item;
        p = target->next;
        target->next = temp;
        temp->next = p;
    }
}

int ds_search(node *pNode,int item){
    node *8target;
    int i;

    for(target = pNode;target->data!=elem && target->next != pNode;++i){
        target = target->next;
    }

    if(target->next == pNode){
        return 0;
    }else{
        return i;
    }
}

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int data;
    struct node *next;
}node;

node *create(int n){
    node *p = NULL;
    node *head;
    p = head;
    node *s;
    int i =1;
    
    if(0 != n){
        while(i<=n){
            s = (node *)malloc(sizeof(node));
            s->data = i++;
            p->next = s;
            p = s;
        }
        s->next = head->next;
    }
    //free(head);
    return s->next;
}

int main(){
    int n = 41;
    int m = 3;
    int i;
    node *p = create(n);
    node *temp;
    
    m %= n;//m = 2
    
    while(p != p->next){
        for(i = 1;i<m-1;i++){
            p = p->next;
        }
        printf("%d->",p->next->data);
        temp = p->next;
        p->next = temp->next;
        
        free(temp);
        p = p->next;
    }
    printf("%d
",p->data);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

#define CardNumber 13

typedef struct node{
    int data;
    struct node *next;
}sqlist,*linklist;

linklist CreateLinkList(){
    linklist head = NULL;
    linklist s,r;
    int i;
    
    r = head;
    
    for(i = 1;i<=CardNumber;i++){
        s = (linklist)malloc(sizeof(sqlist));
        s->data = 0;
        
        if(head == NULL){
            head = s;
        }else{
            r->next = s;
        }
        r = s;
    }
    r->next = head;
    return head;
}

//發(fā)牌順序計(jì)算
void Magician(linklist head){
    linklist p;
    int j;
    int Countnumber =2;
    
    p = head;
    p->data = 1;//第一張牌數(shù)1
    
    while(1){
        for(j = 0;j<Countnumber;j++){
            p = p->next;
            if(p->data != 0){//該位置有牌的話，則下一個(gè)位置
                //p->next;
                j--;
            }
        }
        if(p->data == 0){
            p->data = Countnumber;
            Countnumber++;
            
            if(Countnumber == 14){
                break;
            }
        }
    }
}

int main(){
    linklist head;
    head = CreateLinkList();
    Magician(head);
    
    int i;
    for(i = 0;i<13;i++){
        printf("%d-->",head->data);
        head = head->next;
    }
    return 0;
}

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
    int data;
    struct node *next;
}node;


node * makeList(int n){
    node *head = NULL;
    node *temp;
    node *s;
    int i;
    temp = head;
    
    for(i=1;i<=n;i++){
        s = (node *)malloc(sizeof(node));
        s->data = i;
        
        if(head == NULL){
            head = s;
        }else{
            temp->next = s;
        }
        temp = s;
    }
    temp->next = head;
    return head;
}

int main(){
    int n,i,j,k;
    printf("請輸入方陣的大?。?);
    scanf("%d",&n);
    node * head;
    node * temp;
    head = makeList(n);
    temp = head;
    for(i = 1;i<=n;i++){
        for(j = 1;j<=n;j++){
            printf("%d  ",temp->data);
            temp = temp->next;
        }
        temp = head;
        for(k=1;k<=i;k++){
            temp = temp->next;
        }
        printf("
");
    }
    
    return 0;
    
}

typedef struct DualNode{
    ElemType data;
    struct DualNode *prior;//前驅(qū)節(jié)點(diǎn)
    struct DualNode *next;//后繼節(jié)點(diǎn)
}DualNode，*DualList;

s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;

p->prior->next = p->next;
p->next->prior = p->proor;
free(p);