双链表的建立插入删除算法的实现

1、摘  要 设计一个个人 本，该 本是基于双链表的具体功能实现，双链表的主要功能是查找、删除和插入。其具体的实现过程:依次是建立空指针、构成双向链表、增加结点并给每个结点赋值，最后再通过所建链表进行插入，删除，查找等程序，从而实现了链表问题求解.可以用一般的指针来实现，但是数据库中着重强调了结构体，本题用结构体指针更容易理解和实现和初始化。    关键字：双链表;直接前驱；直接后继；节点；             &#

2、160;                      目  录1  课程设计内容. 62  设计要求. 72.1 问题定义和任务分析. 72.2 逻辑设计. 72.3 详细设计. 82.4程序流程图. 112.5.程序编码. 122.6 程序的调试与测试. 15总结. 18参考文献. 19     &

3、#160;                           1  课程设计内容用C/C+编写一个程序实现双向链表的建立、插入、删除算法。要求建立的链表要有一定的应用价值，具体应用内容设计者自己确定。建立双向链表必须运用结构体建立两个指针，先定义一个双链节点-但是，它的名字必须叫Node，当你派生双向链表时，这样写t

4、emplate calss Type class DblList : public ListnewtypeType ，注意连续的两个""之间要有空格。或者根本不定义这样的结构，直接拿Node类型来做。                               

5、0;    2  设计要求本次设计是基于visual C+作为开发环境，采用双链表的插入删除查找等功能，来实现个人 本的相应功能。2.1 问题定义和任务分析通过题目要求本课题是用C/C+来实现双链表的插入删除查找的功能，具体应用于个人 本， 本中含有存储姓名和 （ 号码使用整型，姓名使用字符型）。双链表的节点中有两个指针域，其一指向直接后继，另一个指向直接前继。和单链表的循环类似，双链表也可以有循环表。在双向链表中，若d为指向表中某一结点的指针（即d为DuLinkList型变量），显然有     

6、; d->next->prior=d->prior->next=d这个表示式恰当地反映了这种结构的特性。2.2 逻辑设计此程序分为三大模块：数据输入模块、数据删除模块、数据查找模块。数据输入模块完成数据的输入和存储，数据删除模块主要完成个人对没用的数据进行删除，数据查找模块方便个人查找存储在里边的数据，函数调用流程图如下：开始初始化链表，调用inlist函数输入数据调用input函数调用deletes函数调用search函数输出进入whlie(1) 结束图21 抽象数据类型定义如下：ADT lnode 数据对象：D=a |a ElemSet，i=1,

7、2,n,n 0 数据关系：R1=<a ,a >|a,a D,i=2,n 基本操作：       void inlist(lnode *p)              操作结果：构造一个链表。   void inputs( lnode *q)       初始条件：链表lnode已存在。  

8、0;  操作结果：向链表中输入数据。            void search(lnode *q)      初始条件：链表lnode已存在。     操作结果：查找链表中的数据。   void deletes(lnode *q)       初始条件：链表lnode已存在。     操作结果：

9、删除链表中的数据。ADT lnode   2.3详细设计typedef struct lnodeent int date; struct lnodeent *next,*prior;/ 表示 循环双链表lnode; Void main()void inlist(lnode *p)   /*初始化链表*/   lnode *nw;               nw = (lnod

10、e *)malloc(sizeof(lnode);  p -> next = nw;  p = nw;    p -> next = head;   if(p -> next != NULL)   p -> next -> prior = p;  p = head -> next;while(p != head)             &#

11、160;                p = p -> next;  Do2）插入函数模块-实现数据的插入指针操作的顺序不是唯一的,但也不是任意    void inputs( lnode *q)    /*插入函数*/         news = (lnode *)malloc(sizeof(ln

12、ode);  news -> next = news -> prior = NULL;  news -> date = b;strcpy(news ->name,k);  for(int i = 0;i < m-1;i+)   q = q -> next;  news -> next = q -> next;  news -> prior = q;          

13、60;        if(q -> next != NULL)   news -> next -> prior = news;  q -> next = news;  q = head -> next;                     &#

14、160;  while(q != head)   q = q -> next; 3）删除函数模块-实现数据的删除void deletes(lnode *q)              /*删除函数*/                   

15、60;q = head; lnode *d;       for(int j = 0;j<k-1;)     q = q->next;   j+;    d = q -> next;  q->next = d -> next;  if(q -> next != NULL)            

16、; /  q -> next -> prior = q;  free(d);  q = head -> next; while(q != head)    q = q -> next;  4）查找函数模块-实现数据的查找void searchs(lnode *q)    /查找函数 q = head;           while(

17、q->next != head)   q = q -> next;  i+;  if(q -> date = h)     break;                          开始初始化链表向 本中输入数据输入（1-4）中的数值，选择相应的判断调用m

18、ain（ ）菜单函数输入是否为4结束调用input函数调用deletes函数调用Search函数While（1）循环输出图22        #include <iostream.h>#include <stdlib.h>#include <stdio.h>#include<string.h>#define exit 0            

19、60;     typedef struct lnode int date; char name20; struct lnodeent *next,*prior;                   / 表示 循环双链表lnode;          

20、;        lnode *head;lnode *creat()                                 /创建头结点 lnode *sq; sq = (lno

21、de *)malloc(sizeof(lnode); sq -> next = sq;    sq -> prior = sq;        return sq;void inlist(lnode *p)                       

22、60;    /*初始化链表*/  lnode *nw;                                   /初始化链表长度    int w; 

23、60;              cout << "   输入 号码本容量：" cin >> w; for(int i = 0;i < w;i+)   nw = (lnode *)malloc(sizeof(lnode);  p -> next = nw;  p = nw;  cout<<"输入 ：&

24、quot;  cin >> p-> date;  cout<<"输入姓名:"  cin>>p->name;  p -> next = head;   if(p -> next != NULL)   p -> next -> prior = p;  p = head -> next; cout << "   号码本为:"<<endl;&#

25、160;while(p != head)                              cout <<" 号码:"<<p -> date<<endl;  cout<<"姓名:"<<p->

26、name<<endl;  p = p -> next;  cout << endl;void inputs( lnode *q)                                 /*插入函数*/ 

27、;   int m,b; char k20; lnode *news; q = head; cout << "输入要插入的位置:" cin >> m;   cout << "输入要插入的 :"  cin >> b;  cout<<"姓名："  cin>>k;  news = (lnode *)malloc(sizeof(lno

28、de);  news -> next = news -> prior = NULL;  news -> date = b;strcpy(news ->name,k);   for(int i = 0;i < m-1;i+)   q = q -> next;  news -> next = q -> next;  news -> prior = q;         

29、0;         if(q -> next != NULL)   news -> next -> prior = news;  q -> next = news;  q = head -> next; cout << "插入后为:"              &#

30、160;     /*删除后输出*/       while(q != head)   cout <<" 号码:"<< q -> date<<endl;cout <<"姓名:"<< q -> name<<endl;  q = q -> next;  cout << endl;void searchs(lno

31、de *q)                       /查找函数 q = head; int h;               cout << "输入查找的 :" cin &

32、gt;> h;                             /h为查找的值 int i = 0;            while(q->next != head) 

33、  q = q -> next;  i+;  if(q -> date = h)     cout << "查找成功! 位置为:" << i << endl;   cout<<" 号码："<<q->date<<endl;   cout<<"姓名"<<q->name<<endl;   br

34、eak;    void deletes(lnode *q)                             /*删除函数*/             

35、           q = head; lnode *d;                                    

36、0;   /要删除的结点 int k;                                      /要删除的位置 cout << "输入删除的

37、位置:" cin >> k;   for(int j = 0;j<k-1;)     q = q->next;   j+;    d = q -> next;  q->next = d -> next;  if(q -> next != NULL)             /  q ->

38、; next -> prior = q;  free(d);  q = head -> next; cout << "删除后为:"<<endl; while(q != head)   cout <<" 号码:"<< q -> date<<endl; cout <<"姓名:"<< q -> name<<endl;  q = q -

39、> next;  cout << endl; void main() int l; lnode *p; head = creat();  p = head; cout << "   初始化链表!"<<endl; inlist(p);                 &

40、#160;         /初始化链表 do   cout << "*输入1选择插入   *输入2选择删除   *输入3选择查询      *输入4退出"<<endl;  cout << "输入:"  cin >> l;  switch(l)    case 1:   inputs(p);   break;  case 2:   deletes(p);   break;  case 3:    searchs(p);       break;    case 4:    exit;