[不指定 2005/11/22 07:53 | by turbozv ]
线性表是《数据结构》正文第一部分的内容,是很简单的,也是很重要的基础知识。对于这部分知识大家应该记得滚瓜烂熟。
     线性表的实现分为顺序(数组)和链表,顺序实现过于简单,这里就不费口水了。
     链表实现有三种类型: 1)单向链表 2)循环链表 3)双向链表


链表的实现有几种形式:(主要是两种表示空节点的方式:NULL和DummyNode哑节点)

A)单链表,头节点NULL为空,尾节点NULL为空
初始化:head = NULL;
x节点后插入t节点:if (x == NULL) { head = t; } else { t->next = x->next; x->next = t;}
删除x后的节点:t = x->next; if (t) { x->next = t->next; free(t); }
遍历: t = head; while(t) { ...; t = t->next; }
是否为空:if (head == NULL) {...}


B)单链表,头节点哑节点为空,尾节点NULL为空
初始化:head = malloc(); head->next = NULL; // 浪费一个节点空间
x节点后插入t节点:t->next = x->next; x->next = t; // 少做一次判断
删除x后的节点:(同A)
遍历: (同A)
是否为空:if (head->next == NULL) {...}


C)单链表,头节点哑节点为空,尾节点哑节点为空 (这个很少用)
初始化:head = malloc(); z = malloc(); head->next = z; z->next = z; // 浪费两个节点空间
x节点后插入t节点:(同B)
删除x后的节点:(同B)
遍历: t = head->next; while (t != z) { ...; t = t->next; }
是否为空:if (head->next == z) {...}


D)循环链表
初始化:head = malloc(); head->next = head;
x节点后插入t节点:(同B)
删除x后的节点:(同B)
遍历: t = head; do { ...; t = t->next; } while (t != head);
是否为空:if (head->next == head) {...}


E)双向循环链表
初始化:head = malloc(); head->next = head->prev = head;
x节点后插入t节点:t->next = x->next; t->prev = x; x->next->prev = t; x->next = t;
删除x节点:x->prev->next = x->next; x->next->prev = x->prev; free(x);
遍历:(同D)
是否为空:(同D)



线性表应用:
1)单向链表
合并两个有序单向链表

pA = lA->next; pB = lB->next;
pC = lC = lA;
while(pA && pB) {
   if (pA->data > pB->data) {
       pC->next = pA; pC = pA; pA = pA->next;
   } else {
       pC->next = pB; pC = pB; pB = pB->next;
   }
}
pC->next = pA? pA : pB;
free(lB);


逆转链表

Link link_Reverse(Link pHead)
{
   Link next, curr = pHead, last = NULL;
   while (curr) {
       next = curr->next; curr->next = last;
       last = curr; curr = next;
   }
   return last;
}



2)循环链表
Josephus问题

int i;
Link pHead, pNode, pTmp;
pHead = (Link) malloc(sizeof(struct _link));
pHead->item = 1;
pHead->next = pHead;
for (i=2; i<=N; i++) {
   pNode = (Link) malloc(sizeof(struct _link));
   pNode->item = i;
   pNode->next = pHead->next;
   pHead->next = pNode;
   pHead = pNode;
}
pNode = pHead;
while (pNode->next != pNode) {
   for (i=1; i<M; i++)
       pNode = pNode->next;
   pTmp = pNode->next;
   pNode->next = pTmp->next;
   free(pTmp);
}
printf("%dn", pNode->item);
free(pNode);



转载请注明出处,谢谢!
学习 | 评论(1) | 引用(0) | 阅读(11088)
chrislgh
2005/11/26 10:10
删除x后的节点:t = x->next; if (t != NULL) &leftsign; x->next = t->next; free(t); &rightsign;
管理员 回复于 2005/11/26 22:54
nodnod :)
分页: 1/1 第一页 1 最后页