3-线性表链式存储-双向链表

熬夜的凝视

这几天略荒废人生，还剩157天了，我要发愤图强！

熬夜先把前几天拉下的工作完善了……

【注】

1、双向链表实现和单链表基本类似，但是需要修改prior指针：修改时应注意判断后一位是否为空，避免出错。

2、showList输出展示时是逆序输出。

  1 #include<iostream>
  2 #include<cstdlib>
  3 using namespace std;
  4 #define ture 1
  5 #define false 0
  6 #define maxsize 50
  7 #define listincreament 10
  8 #define ok 1
  9 #define error -3
 10 #define overflow -2
 11 typedef int Status;
 12 typedef int ElemType;
 13 typedef struct LNode
 14 {
 15     ElemType data;
 16     struct LNode *next,*prior;
 17 } LNode,*LinkList;
 18 //头插法建双向链表
 19 void CreatList_head(LinkList &L,int length)//头插法
 20 {
 21     LNode *s,*p;
 22     int x;
 23     L=(LinkList)malloc(sizeof(LNode));
 24     L->next=NULL;//创建头结点
 25     L->prior=NULL;
 26     p=L;
 27     while(length--)
 28     {
 29         cin>>x;
 30         s=(LNode *)malloc(sizeof(LNode));
 31         s->data=x;
 32 
 33         s->next=p->next;
 34         s->prior=p;
 35         if(p->next!=NULL)//(*)
 36             p->next->prior=s;
 37         p->next=s;
 38     }
 39 
 40 }//需要注意的点：插入时由于要修改指针，最开始头指针前后为空，在修改后一个指针的prior时需要加入(*)式判断。
 41 
 42 
 43 void CreatList_tail(LinkList &L,int length)//尾插法
 44 {
 45     LNode *p,*s;//p为工作指针
 46     int x;
 47     L=(LinkList)malloc(sizeof(LNode));
 48     L->next=NULL;
 49     L->prior=NULL;
 50     p=L;
 51     while(length--)
 52     {
 53         cin>>x;
 54         s=(LNode *)malloc(sizeof(LNode));
 55         s->data=x;
 56         p->next=s;
 57         s->next=NULL;
 58         s->prior=p;
 59         p=p->next;
 60     }
 61 }
 62 
 63 LNode* GetElem_order(LinkList &L,int n)//按序号查找节点
 64 {
 65     LNode *p=L;
 66     while(p!=NULL&&n>0)
 67     {
 68         p=p->next;
 69         n--;
 70 
 71     }
 72     return p;
 73 }
 74 
 75 void InsertLNode(LinkList &L,ElemType elem,int pos)//在第pos个位置插入元素
 76 {
 77     LNode *p=L,*s;
 78     pos--;
 79     while(pos>0)
 80     {
 81         p=p->next;
 82         pos--;
 83     }
 84     s=(LNode *)malloc(sizeof(LNode));
 85     s->data=elem;
 86     s->next=p->next;
 87     s->prior=p;
 88     p->next->prior=s;
 89     p->next=s;
 90 }
 91 
 92 void DeleteList_order(LinkList &L,int pos)//删除指定序号的节点
 93 {
 94     LNode *p=GetElem_order(L,pos-1);//即为删除指定节点前一位的后一个
 95     LNode *q=p->next;
 96     p->next=q->next;
 97     q->next->prior=p;
 98     free(q);
 99 }
100 
101 void showList(LinkList &L)//输出是倒着输出的！
102 {
103     LNode *p=L->next;
104     while(p->next!=NULL)
105     {
106         p=p->next;
107     }
108     while(p!=L)
109     {
110         cout<<p->data;
111         if(!(p->next==L))
112         {
113             cout<<' ';
114         }
115          p=p->prior;
116     }
117     cout<<endl;
118 }
119 void showpoint(LNode *p)//展示特定节点的信息
120 {
121     if(p!=NULL)
122         cout<<p->data<<endl;
123     else cout<<"not found."<<endl;
124 }
125 
126 int main()
127 {
128     LNode *L1,*L2,*pos;
129     CreatList_head(L1,10);
130     //CreatList_tail(L2,7);
131     showList(L1);
132     DeleteList_order(L1,5);
133     showList(L1);
134     InsertLNode(L1,88,4);
135     showList(L1);
136    // showList(L2);
137 }

2、功能小算法实现

注：用我上面写的代码测试的时候先整一个循环双链表……

 1 /*判断一个循环双链表是否对称*/
 2 int symmetry(LinkList &L)
 3 {
 4     LNode *p=L->next,*q=L->prior;
 5     while(p!=q&&p->next!=q)
 6     {
 7         if(p->data==q->data)
 8         {
 9             p=p->next;
10             q=q->prior;
11         }
12         else return 0;
13     }
14     return 1;
15 }

3-线性表 链式存储-双向链表

3-线性表链式存储-双向链表