第一章线性表

线性表的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include<cstdio>
#include<iostream>
using namespace std;
const int maxSize=100010;
typedef struct{
    int data[maxSize];
    int length;
}SqList;
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;

typedef struct DLNode{
    int data;
    struct DLNode *prior;
    struct DLNode *next;
}DLNode,*DLinkList;

//插入操作
int insertElem(Sqlist &L,int index,int x){
    if(index<0||index>length-1||index==maxSize)
        return 0;
    for(int i=L.length-1;i>=index;i--){
        L.data[i+1]=L.data[i];
    }
    L.data[index]=x;
    L.length++;
    return 1;
}

//删除操作
int deleteElem(Sqlist &L,int index){
    if(index<0||index>length-1||index==maxSize)
        return 0;
    for(int i=index;i<L.length-1;i++){
        L.data[i]=L.data[i+1];
    }
    L.length--;
    return 1;
}

//按值查找
int findElem(Sqlist L,int x){
    for(int i=0;i<=L.length-1;i++){
        if(L.data==x){
            return i;
        }
    }
    return -1;
}

//单链表的头插建表
LinkList List_HeadInsert(Linklist &L){
    LNode *s;
    int x;
    L=(LinkedList)malloc(sizeof(LNode));
    L->next=NULL;
    cin>>x;
    while(x!=9999){
       s=(LNode)malloc(sizeof(LNode));
       s->data=x;
       s->next=L->next;
       L->next=s;
       cin>>x;
    }
    return L;
}

//尾插法建立单链表
LinkList List_TailInsert(Linklist &L){
    int x;
    L=(LinkedList)malloc(sizeof(LNode));
    L->next=NULL;
    LNode *s;
    LNode *r=L;
    while(x!=9999){
       s=(LNode)malloc(sizeof(LNode));
       s->data=x;
       r->next=s;
       r=s;
       cin>>x;
    }
    r->next=NULL;
    return L;
}


//按序号查找结点
LNode *GetElem(LinkList L,int index){
    if(index<0)
        return NULL;
    int cnt=0;
    LNode *p=L;
    while(p!=NULL&&cnt<index){
        p=p->next;
        cnt++;
    }
    return p;
}

//按值查找结点
LNode *LocaledElem(LinkList L,Elemtype e){
    LNode *p=L->next;
    while(p!=NULL&&p->data!=e){
        p=p->next;
    }
    return p;
}

//插入结点 插入s到index位置前面
int InsertElem(LinkList &L,LNode s,int index){
    if(index<0)
        return 0;
    int cnt=0;
    LNode *p=L->next;
    while(p!=NULL&&cnt<index-1){
        p=p->next;
        cnt++;
    }
    s->next=p->next;
    p->next=s;
    return 1;
    
}

//按位置删除结点
int DeleteElem(LinkList &L,int index){
    if(index<0) return 0;
    int cnt=0;
    LNode *p=L->next;
    while(p!=NULL&&cnt<index-1){
        p=p->next;
        cnt++;
    }
    LNode *q;
    q=p->next;
    p->next=q->next;
    free(p);
    return 1;
}

//按值删除结点
void Delete_LinkList(LinkList &L,int key){
    LNode *p=L,*q=L->next;
    while(p!=NULL&&q->data!=key){
        p=q;
        q=q->next;
    }
    if(q->data==key){
        p->next=q->next;
        free(q);
    }else{
        cout<<"所要删除的结点不存在\n";
    }
}

//双链表
void db(DLinkList &L){
//插入操作
    s->next=p->next;
    s->prior=p;
    p->next->prior=s;
    p->next=s;
//删除操作
    p->next=q->next;
    q->next->prior=p;
    free(q);
}

//循环链表
/*
判断是否为空：head->next==head;
判断是否是表尾结点：p->next==head;
*/

删除带头结点的单链表最小结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void delMinNode(Linklist &L){
    if(L==NULL||L->next==NULL)
        return;
    LNode *pre=L;
    LNode *minpre=L;
    LNode *p=L->next;
    LNode *minp=p;
    while(p){
        if(p->data<minp->data){
            minp=p;
            minpre=pre;
        }
        pre=p;
        p=p->next;
    }
    minpre->next=minp->next;
    free(minp);
}

逆序带头结点的单链表

1
2
3
4
5
6
7
8
9
10
11
12
LinkList reversList(LinkList &L){
    LNode *p=L->next;
    LNode *q=p->next;
    L->next=NULL;
    while(p!=NULL){
        p->next=L->next;
        L->next=p;
        p=q;
        q=q->next;
    }
    return L;
}

倒数第k个结点的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Find(LinkList L,int k){
    LNode *p=L->next;
    LNode *q=L->next;
    for(int i=1;i<k;i++){
        p=p->next;
        if(p==NULL)
            return -1;
    }
    while(p!=NULL){
        p=p->next;
        q=q->next;
    }
    return q->data;
}

合并递增序列为新的单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Merge(LinkList A,LinkList B,LinkList &C){
    LNode *p=A->next;
    LNode *q=B->next;
    C=A;
    C->next=NULL;
    LNode *r=C;
    while(p!=NULL&&q!=NULL){
        if(p->data<q->data){
            r->next=p;
            p=p->next;
            r=r->next;
        }else{
            r->next=q;
            q=q->next;
            r=r->next;
        }
    }
    r->next=NULL;
    if(p!=NULL)r->next=p;
    if(q!=NULL)r->next=q;
}

x插入到L使L仍递增有序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void InsertList(SqList &L,int x){
    int t;
    for(int i=0;i<L.length;i++){
        if(L.data[i]>x){
            t=i;
            break;
        }
    }
    for(int i=0;i<L.length;i++){
        L.data[i+1]=L.data[i];
    }
    L.data[t]=x;
    L.length++;
}

顺序表逆置

1
2
3
4
5
6
7
8
9
void reserve(SqList &L){
    int t;
    for(int i=0;i<L.length/2;i++){
        t=L.data[i];
        L.data[i]=L.data[L.length-i-1];
        L.data[L.length-i-1]=t;
    }
}

删除无序链表中重复的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void DeleteList(LinkList &L){
    LNode *p,*q,*s;
    p=L->next;
    while(p){
        q=p;
        while(q->next!=NULL){//删除又有等于p的结点 待删除的点是q->next
            if(p->data==q->next->data){
                s=q->next;
                q->next=s->next;
                free(s);
            }else
                q=q->next;
        }
        p=p->next;
    }
}

删除有序链表中重复的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void del(Linklist &L){
    LNode *p=L->next;
    LNode *q=p->next;
    while(p){
        if(p->data==q->data){
            p->next=q->next;
            free(q);
            q=p->next; 
        }else{
            p=q;
            q=q->next;
        }
    }
}

两个链表是否存在公共结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// bool same(Linklist A,Linklist B){
//     LNode *p=A->next;
//     LNode *q=B->next;
//     while(q){
//         p=A->next;
//         while(p){
//             if(p->next==q){
//                 return 1;
//             }else{
//                 p=p->next;
//             }
//         }
//         q=q->next;
//     }
//     return 0;
// }

int getLength(Linklist L){
    int len=0;
    LNode *p;
    p=L->next;
    while(p){
        len++;
        p=p->next;
    }
    return len;
}
LinkList Search(LinkList L1,LinkList L2){
    int len1=getLength(L1);
    int len2=getLength(L2);
    int dist=max(len1,len2)-min(len1,len2);
    LinkList longlist,shortList;
    if(len1>len2){
        longList=L1->next;
        shortList=L2->next;
    }else{
        shortList=L1->next;
        longList=L2->next;
    }
    while(dist--)
        longList=longList->next;
    while(longList!=NULL){
        if(longList==shortList)
            return longList;
        else{
            longList=longList->next;
            shortList=shortList->next;
        }
    }
}