1、存取方式
1）順序表：可以順序存取，也可以隨機存取，
2）鏈表：只能從表頭順序存取，
2、邏輯結構與物理結構
1）順序存盤：邏輯上相鄰，物理位置相鄰，
2）鏈式存盤：邏輯上相鄰，物理位置不一定相鄰，
3、查找、插入、洗掉
1）按值查找：當表中資料無序時，順序表和鏈表，時間復雜度為O(n)，
當表中資料有序時，順序表可采用折半查找，時間復雜度為O(log2n)，
2）按序號查找：順序表，時間復雜度為O(1)，
鏈表，時間復雜度為O(n)，
3）插入和洗掉：順序表，平均需要移動半個表長的元素
鏈表，只需修改相關結點的指標域，
4、單鏈表中一些簡單題目的解決
1）L為帶頭結點的單鏈表，洗掉L中所有值為x的結點
void delx1(Linklist &L, int x)
{
LNode * p = L->next, *pre = L, *q;
while (p!=NULL)
{
if (p->data =https://www.cnblogs.com/xqy1874/p/= x)
{
q = p;
p = p->next;
pre->next = p;
free(q);
}
else
{
pre = p;
p = p->next;
}
}
}
void delx2(Linklist &L, int x)
{
LNode * p = L->next, *r = L, *q;
while (p!=NULL)
{
if (p->data != x)
{
r->next = p;
r = p;
p = p->next;
}
else
{
q = p;
p = p->next;
free(q);
}
}
r->next = NULL;
}
2）用遞回實作洗掉L中所有值為x的結點
void delx3(Linklist &L, int x)
{
LNode * p;
if (L == NULL)
{
return;
}
if (L->data =https://www.cnblogs.com/xqy1874/p/= x)
{
p = L;
L = L->next;
free(p);
delx3(L, x);
}
else
{
delx3(L->next, x);
}
}
3）L為帶頭結點的單鏈表，洗掉L中最小值結點
Linklist delmin(Linklist &L)
{
LNode * pre = L, *p = pre->next;
LNode * minpre = pre, *minp = p;
while (p!=NULL)
{
if (p->data < minp->data)
{
minp = p;
minpre = pre;
}
pre = p;
p = p->next;
}
minpre->next = minp->next;
free(minp);
return L;
}
4）L為遞增有序的單鏈表，洗掉表中值相同的元素
void delsame(Linklist &L)
{
LNode * p = L->next, *q;
if (p == NULL)
{
return;
}
while (p->next!=NULL)
{
q = p->next;
if (p->data =https://www.cnblogs.com/xqy1874/p/= q->data)
{
p->next = q->next;
free(q);
}
else
{
p = p->next;
}
}
}
5）L為帶頭結點的單鏈表，將L就地逆置
Linklist reverse1(Linklist L)
{
LNode * p, *r;
p = L->next;
L->next = NULL;
while (p!=NULL)
{
r = p->next;
p->next = L->next;
L->next = p;
p = r;
}
return L;
}
Linklist reverse2(Linklist L)
{
LNode * pre, *p = L->next, *r = p->next;
p->next = NULL;
while (r!=NULL)
{
pre = p;
p = r;
r = r->next;
p->next = pre;
}
L->next = p;
return L;
}
6）將單鏈表L結點重排，使遞增有序
void sort(Linklist &L)
{
LNode * p = L->next, *pre;
LNode * r = p->next;
p->next = NULL;
p = r;
while (p!=NULL)
{
r = p->next;
pre = L;
while (pre->next != NULL && pre->next->data<p->data)
{
pre = pre->next;
}
p->next = pre->next;
pre->next = p;
p = r;
}
}
7）帶頭結點的單鏈表L，頭指標為head，遞增輸出表中資料
void del(Linklist &head)
{
LNode * p, * pre,* q;
while (head->next!=NULL)
{
pre = head;
p = pre->next;
while (p->next!=NULL)
{
if (p->next->data < pre->next->data)
{
pre = p;
}
p = p->next;
}
printf("%d",pre->next->data);
q = pre->next;
pre->next = q->next;
free(q);
}
free(head);
}
8）將表A中的資料按序號的就奇偶性分解到表AB中,對B表的建立采用尾插法
Linklist listcreat1(Linklist &A)
{
Linklist B;
int i = 0;
B = (Linklist)malloc(sizeof(LNode));
B->next = NULL;
LNode * ra = A, * rb = B,* p;
p = A->next;
A->next = NULL;
while (p!= NULL)
{
i++;
if (i % 2 == 0)
{
rb->next = p;
rb = p;
}
else
{
ra->next = p;
ra = p;
}
p = p->next;
}
ra->next = NULL;
rb->next = NULL;
return B;
}
9）將表A中的資料按序號的就奇偶性分解到表AB中,對B表的建立采用頭插法
Linklist listcreat2(Linklist &A)
{
Linklist B = (Linklist)malloc(sizeof(LNode));
B->next = NULL;
LNode * p = A->next, * q;
LNode * ra = A;
while (p!=NULL)
{
ra->next = p;
ra = p;
p = p->next;
q = p->next;
p->next = B->next;
B->next = p;
p = q;
}
ra->next = NULL;
return B;
}
10）把柄兩個遞增有序單鏈表帶頭結點，和并后鏈表遞減排列
void listmerge(Linklist &La, Linklist &Lb)
{
LNode * r, *pa = La->next, *pb = Lb->next;
La->next = NULL;
while (pa&&pb)
{
if (pa->data <= pb->data)
{
r = pa->next;
pa->next = La->next;
La->next = pa;
pa = r;
}
else
{
r = pb->next;
pb->next = La->next;
La->next = pb;
pb = r;
}
}
if (pa)
{
pb = pa;
}
while (pb)
{
r = pb->next;
pb->next = La->next;
La->next = pb;
pb = r;
}
free(Lb);
}
11）將鏈表AB中的公共元素組成鏈表C
void getcom(Linklist A, Linklist B)
{
LNode * p = A->next, *q = B->next, *r, *s;
Linklist C = (Linklist)malloc(sizeof(LNode));
r = C;
while (p!=NULL&&q!=NULL)
{
if (p->data < q->data)
{
p = p->next;
}
else if(p->data>q->data)
{
q = q->next;
}
else
{
s = (LNode *)malloc(sizeof(LNode));
s->data = https://www.cnblogs.com/xqy1874/p/p->data;
r->next = s;
r = s;
p = p->next;
q = q->next;
}
}
r->next = NULL;
}
12）將兩個鏈表進行集合相等的值只保留一個，將其余結點釋放
Linklist listunion(Linklist &la, Linklist &lb)
{
LNode * pa, * pb,* pc,* pu;
pa = la->next;
pb = lb->next;
pc = la;
while (pa&&pb)
{
if (pa->data =https://www.cnblogs.com/xqy1874/p/= pb->data)
{
pc->next = pa;
pc = pa;
pa = pa->next;
pu = pb;
pb = pb->next;
free(pu);
}
else if (pa->data < pb->data)
{
pu = pa;
pa = pa->next;
free(pu);
}
else
{
pu = pb;
pb = pb->next;
free(pu);
}
}
while (pa)
{
pu = pa;
pa = pa->next;
free(pu);
}
while (pb)
{
pu = pb;
pb = pb->next;
free(pu);
}
pc->next = NULL;
free(lb);
return la;
}
13）單鏈表AB，判斷B是否是A的子序列
int pattern(Linklist A, Linklist B)
{
LNode * p = A, *pre = p, *q = B;
while (p&&q)
{
if (p->data =https://www.cnblogs.com/xqy1874/p/= q->data)
{
p = p->next;
q = q->next;
}
else
{
pre = pre->next;
p = pre;
q = B;
}
}
if (q == NULL)
{
return 1;
}
else
{
return 0;
}
}
5、鏈表的一些簡單問題的實作
1）從兩頭掃描回圈雙鏈表，判斷是否對稱
int symmetry(DLinklist L)
{
DNode * p = L->next, *q = L->prior;
while (p!=q&&p->next!=q)
{
if (p->data =https://www.cnblogs.com/xqy1874/p/= q->data)
{
p = p->next;
q = q->prior;
}
else
{
return 0;
}
}
return 1;
}
2）每次洗掉回圈單鏈表中最小的元素，直到鏈表為空
void delall(Linklist &L)
{
LNode * p, *pre, *minp, *minpre;
while (L->next != L)
{
p = L->next;
pre - L;
minp = p;
minpre = pre;
while (p != L)
{
if (p->data < minp->data)
{
minp = p;
minpre = pre;
}
pre = p;
p = p->next;
}
printf("%d", minp->data);
minpre->next = minp->next;
free(minp);
}
free(L);
}
3）將回圈鏈表h2鏈接到回圈鏈表h1之后，使之仍保持回圈鏈表的形式
Linklist link(Linklist &h1, Linklist &h2)
{
LNode * p, *q;
p = h1;
while (p->next!=h1)
{
p = p->next;
}
q = h2;
while (q->next!=h2)
{
q = q->next;
}
p->next = h2;
q->next = h1;
return h1;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/198921.html
標籤：其他
上一篇：線索二叉樹（C語言描述）