数据结构(C语言版)---顺序表与链表的比较

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 == 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 == 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 == 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 = 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 == 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 == 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 == 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;
}

上一篇:C++ 双链表


下一篇:公交线路管理