双向链表

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define sc scanf
  4 #define pr printf
  5 
  6 typedef struct LNode
  7 {
  8     int data;
  9     struct LNode *prior;
 10     struct LNode *next;
 11 }LNode,*LinkList;
 12 
 13 int tot = 0;
 14 //创建双向链表 
 15 void Create_LinkList(LinkList &L,int n)
 16 {
 17     L = (LNode *)malloc(sizeof(LNode));
 18     L->data = n + 1; 
 19     LNode *q = L;
 20     
 21     for(int i = 1;i < n;i++)
 22     {
 23         LNode *p = (LNode *)malloc(sizeof(LNode));
 24         sc("%d",&p->data);
 25         q->next = p;
 26         p->prior = q;
 27         q = p;
 28     }
 29 
 30     if(n)
 31     {
 32         LNode *p = (LinkList)malloc(sizeof(LNode));
 33         sc("%d",&p->data);
 34         q->next = p;
 35         p->prior = q;
 36         p->next = L;
 37         L->prior = p;
 38     }
 39     else
 40     {
 41         L->next = L;
 42         L->prior = L;
 43     }
 44 
 45 }
 46 
 47 //获取双向链表第i个元素的指针位置
 48 LinkList getelem_pos(LinkList &L,int i)
 49 {
 50     int cnt = 0;
 51     LNode *p = L;
 52     while(p->next != L && cnt < i)
 53     {
 54         cnt++;
 55         p = p->next;
 56     }
 57     if(cnt == i)
 58     return p;
 59     else {
 60         puts("position is invalid! Please re-enter.");
 61         return NULL;
 62     }
 63 } 
 64 
 65 //双向链表插入元素
 66 bool insert(LinkList &L,int i,int e)
 67 {
 68     LNode *p,*q;
 69     if(!(p = getelem_pos(L,i)))//该位置不合法 
 70     return 0;
 71     //cout << "hello" << endl;
 72     
 73     LNode *s = (LNode *)malloc(sizeof(LNode));
 74     
 75 //    if(s == NULL);//堆内存分配失败 
 76 //    return 0;
 77     
 78     q = p->prior; //第i-1个结点
 79      
 80     s->data = e;
 81     
 82     q->next = s;
 83     s->prior = q;
 84     
 85     s->next = p;
 86     p->prior = s;
 87     
 88     return 1; 
 89 } 
 90 
 91 //删除第i个元素
 92 bool delete_LinkList(LinkList &L,int i,int &e)
 93 {
 94     LNode *p,*q;
 95     p = getelem_pos(L,i);
 96     
 97     if(p == NULL) return 0; //该位置不合法 
 98     //cout << p->data << endl;
 99     e = p->data;
100     q = p->prior;
101     q->next = p->next;
102     (p->next)->prior = q;
103     free(p);
104     return 1;
105 } 
106 
107 //遍历双向链表 
108 void deLinkList_Traver(LinkList &L)
109 {
110    LNode *p = L;
111    while(p->next != L)
112    {
113        p = p->next;
114        tot++;
115        cout << p->data << " " << (p->prior)->data << " " << (p->next)->data << endl;
116    }
117    //puts("");
118 }
119 
120 //销毁链表 
121 void delete_Link(LinkList &L)
122 {
123     int k;
124      for(int i = 1;i <= tot;i++)
125      delete_LinkList(L,1,k);
126      
127      free(L);//销毁头结点 
128 }
129 int main()
130 {
131     int n;
132     tot = 0;
133     LinkList L;
134     sc("%d",&n);
135     Create_LinkList(L,n);
136     deLinkList_Traver(L);
137     bool ok = insert(L,2,7);
138     //cout << ok << endl;
139     cout << endl;
140     if(ok)
141     {
142         deLinkList_Traver(L);
143     }
144     
145     int e;
146     ok = delete_LinkList(L,1,e);
147     cout << endl;
148     if(ok)
149     {
150         deLinkList_Traver(L);
151     }
152     
153 //    delete_Link(L);
154 //    deLinkList_Traver(L);
155     return 0;
156 }