Question

l数据结构~~双链表的实现？

Answer 1

双链表
　　1、双向链表（Doubly Linked List）
　　双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。
　　注意：
　　①双链表由头指针head惟一确定的。
　　②带头结点的双链表的某些运算变得方便。
　　③将头结点和尾结点链接起来，为双（向）循环链表。
　　2、双向链表的结点结构和形式描述
　　①结点结构(见上图a)
　　②形式描述
　　typedef struct dlistnode{
　　DataType data;
　　struct dlistnode *prior,*next;
　　}DListNode;
　　typedef DListNode *DLinkList;
　　DLinkList head;
　　3、双向链表的前插和删除本结点操作
　　刻画双链表结构的对称性的语句：p→prior→next== p→next→prior;由于双链表的对称性，在双链表能能方便地完成各种插入、删除操作。
　　①双链表的前插操作
　　void DInsertBefore(DListNode *p,DataType x)
　　{//在带头结点的双链表中，将值为x的新结点插入*p之前，设p≠NULL
　　DListNode *s=malloc(sizeof(DListNode));//①
　　s->data=x;//②
　　s->prior=p->prior;//③
　　s->next=p;//④
　　p->prior->next=s;//⑤
　　p->prior=s;//⑥
　　}
　　②双链表上删除结点*p自身的操作
　　void DDeleteNode(DListNode *p)
　　{//在带头结点的双链表中，删除结点*p，设*p为非终端结点
　　p->prior->next=p->next;//①
　　p->next->prior=p->prior;//②
　　free(p);//③
　　}
　　注意：
　　与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。
　　上述两个算法的时间复杂度均为O(1)。

Answer 2

给你一段代码
#include <stdlib.h>
#include <stdio.h>
/*――――――――――――双向链表的定义――――――――――――*/
struct llist
{
struct llist *prior;
int num;
struct llist *next;
};
typedef struct llist node;
typedef node *llink;
/*――――――――――――双向链表的输出――――――――――――*/
void printllist(llink head)
{
llink ptr;
ptr = head->next;
while ( ptr != NULL )
{
printf("[%d]",ptr->num);
ptr = ptr->next;
}
printf("\n");
}
/*――――――――――――双向链表的倒序输出――――――――――*/
void printllist2(llink head)
{
llink ptr;
ptr = head;
while( ptr->next != NULL ){
ptr=ptr->next;
}
while ( ptr != head )
{
printf("[%d]",ptr->num);
ptr = ptr->prior;
}
printf("\n");
}
/*――――――――――――双向链表的创建―――――――――――*/
llink createllist(int *array,int len)
{
llink head; /* 双向链表的开始指针 */
llink ptr,ptr1;
int i;
/* 建立开头结点 */
head = ( llink ) malloc(sizeof(node)); /* 分配内存 */
if ( !head ) /* 检查指针 */
return NULL;
ptr = head;/* 将ptr指向链表开始 */
for ( i = 0; i < len; i++ ) /* 建立其它结点回路 */
{
ptr1 = ( llink ) malloc(sizeof(node));
if ( !ptr1 )
return NULL;
ptr1->num = array[i]; /* 建立结点内容 */
ptr1->next = NULL; /* 设定指针初值 */
ptr1->prior = NULL;
ptr->next = ptr1; /* 连接结点 */
ptr1->prior = ptr;
ptr = ptr->next;
}
return head;
}
/*―――――――――――双向链表的结点插入――――――――――*/
llink insertnode(llink head,llink ptr,int value)
{
llink new1,ptr1=head; /* 新结点指针变量 */
while(ptr1!=ptr)
ptr1=ptr1->next;
if(!ptr1){
printf("找不到插入位置，插入位置有误\n");
return head;
}
new1= ( llink ) malloc(sizeof(node));
if ( !new1 )
return NULL;
new1->num = value; /* 设定初值 */
new1->next = NULL;
new1->prior = NULL;
new1->next = ptr->next;/* 交换4个指针*/
ptr->next->prior = new1;
ptr->next = new1;
new1->prior = ptr;
return head;/* 返回头结点 */
}
/*―――――――――――双向链表的结点删除――――――――――－*/
llink deletenode(llink head,llink ptr)
{
if(!(head->next)) {/* 链表为空直接返回头指针 */
printf("删除链表为空\n");
return head;
}
llink previous;
previous = head;
if(ptr){
while ( previous->next != ptr ) /* 找结点ptr前一结点 */
previous = previous->next;
/* 找结点ptr前一结点之后进行删除操作 */
previous->next = ptr->next;
ptr->next->prior=previous; /* 删除中间结点 */
}
else{
while ( previous->next->next != NULL )
previous = previous->next;
ptr= previous->next;
previous->next = ptr->next;
}
free(ptr);
return head;/* 返回头结点 */
}
/*―――――――――――――主程序――――――――――――――*/
void main(){
int llist1[6] = { 1, 2, 3, 4, 5, 6 };
llink head;
/* 建立链表并输出*/
head = createllist(llist1,6);
if ( !head )
{
printf("内存分配失败! \n");
exit(1);
}
printf("原来的链表: ");
printllist(head);
/* 插入新结点(在表头插入元素"0")*/
head = insertnode(head,head,0);
if ( !head )
{
printf("内存分配失败! \n");
exit(1);
}
printf("插入结点后的链表: ");
printllist(head);
/* 删除链内结点(删除第三个结点) */
head = deletenode(head,head->next->next->next);
printf("删除结点后的链表: ");
printllist(head);
/* 倒序输出链表元素 */
printf("链表的倒序输出: ");
printllist2(head);
}
/*―――――――――――――结束――――――――――――――*/

Answer 3

哦哦 学习 学习 呵呵