單向連結清單:
1 #include <cstdio>
2 using namespace std;
3 struct LNode{
4 int data;
5 struct LNode * next;
6 };
7 struct LinkList{
8 LNode * head,tail;
9 int len;
10 };
11 void InitList(LinkList &L){
12 L.len = 0;
13 L.head->next = NULL;
14 }
15 void CreateList_L(LinkList &L,int n){
16 L.len = n;
17 LNode* & head = L.head;
18 head = new LNode();
19 head -> next =NULL;
20 while(n--){
21 LNode *p = new LNode();
22 scanf("%d",&p->data);
23 p->next = head->next;
24 head->next=p;
25 }
26 }
27 void CreateList(LinkList &L,int n){
28 L.len = n;
29 L.head = new LNode;
30 LNode *p = L.head;
31 while(n--){
32 LNode * t =new LNode();
33 scanf("%d",&t->data);
34 p->next = t;
35 p = t;
36 }
37 p->next = NULL;
38 }
39 void ListTraverse(LinkList L,void (visit)(LNode*)){
40 LNode *p =L.head->next;
41 while(p!=NULL){
42 visit(p);
43 p = p->next;
44 }
45 }
46 int ListInsert_L(LinkList &L,int i, int data){
47 LNode * p =L.head;
48 int j = 0;
49 while(p&&j++<i ){
50 p=p->next;
51 }
52 if(!p || i<0)return 0;
53 LNode *t = new LNode();
54 t->data = data;
55 t->next = p->next;
56 p->next = t;
57 L.len++;
58 return 1;
59 }
60 int ListDelete_L(LinkList &L,int i,int &data){
61 LNode *p = L.head;
62 int j=0;
63 while(p&&j++<i){
64 p = p->next;
65 }
66 if(!(p->next) || i <0)return 0;
67 LNode *t = p->next;
68 p->next = p->next->next;
69 data=t->data;
70 delete t;
71 L.len--;
72 return 1;
73 }
74 int GetElem_L(LinkList L,int i,int &data){
75 LNode *p = L.head;
76 int j=0;
77 while(p && j++<=i) p=p->next;
78 if(!p|| i<0 )return 0;
79 data=p->data;
80 return 1;
81 }
82 int MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){
83 LNode *pa = La.head -> next;
84 LNode *pb = Lb.head -> next;
85 Lc.head=new LNode();
86 LNode *pc = Lc.head;
87 while(pa&&pb){
88 if(pa->data < pb->data){
89 pc->next = pa;
90 pa = pa->next;
91 }
92 else{
93 pc->next = pb;
94 pb = pb->next;
95 }
96 pc = pc -> next;
97 }
98 pc->next = pa == NULL?pb:pa;
99 }
100 void visit(LNode *p){
101 printf("%d\n",p->data);
102 }
103 int main(){
104 LinkList list,list2,list3 ;
105 // InitList(list);
106 CreateList(list,5);
107 CreateList(list2,5);
108 MergeList(list,list2,list3);
109 //ListInsert_L(list,-1,6);
110 //int v =123;
111 //GetElem_L(list,4,v);
112 //printf("%d",v);
113 ListTraverse(list3,visit);
114 return 0;
115 }
循環連結清單:
1 #include <cstdio>
2 #include <stack>
3 using namespace std;
4 struct LNode{
5 int data;
6 struct LNode * next;
7 };
8 struct LinkList{
9 LNode * head,*tail;
10 int len;
11 };
12 void CreateList_L(LinkList &L,int n){
13 L.len = n;
14 LNode* & head = L.head;
15 head = new LNode();
16 head -> next =head;
17 while(n--){
18 LNode *p = new LNode();
19 scanf("%d",&p->data);
20 p->next = head->next;
21 head->next=p;
22 }
23 }
24 void CreateList(LinkList &L,int n){
25 L.len = n;
26 L.head = new LNode;
27 LNode *p = L.head;
28 while(n--){
29 LNode * t =new LNode();
30 scanf("%d",&t->data);
31 p->next = t;
32 p = t;
33 }
34 p->next = L.head;
35 }
36 void ListTraverse(LinkList L,void (visit)(LNode*)){
37 LNode *p =L.head->next;
38 while(p!=L.head){
39 visit(p);
40 p = p->next;
41 }
42 }
43 int ListInsert_L(LinkList &L,int i, int data){
44 LNode * p =L.head;
45 int j = 0;
46 while((p!=L.head||!j)&&j++<i){
47 p = p->next;
48 }
49 if( p == L.head&&j || i<0)return 0;
50 LNode *t = new LNode();
51 t->data = data;
52 t->next = p->next;
53 p->next = t;
54 L.len++;
55 return 1;
56 }
57 int ListDelete_L(LinkList &L,int i,int &data){
58 LNode *p = L.head;
59 int j=0;
60 while((p!=L.head||!j)&&j++<i){
61 p = p->next;
62 }
63 if((p->next)==L.head || i <0)return 0;
64 LNode *t = p->next;
65 p->next = p->next->next;
66 data=t->data;
67 delete t;
68 L.len--;
69 return 1;
70 }
71 int GetElem_L(LinkList L,int i,int &data){
72 LNode *p = L.head;
73 int j=0;
74 while((p!=L.head||!j) && j++<=i) p=p->next;
75 if(p==L.head&&j|| i<0 )return 0;
76 data=p->data;
77 return 1;
78 }
79 void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){
80 LNode *pa = La.head -> next;
81 LNode *pb = Lb.head -> next;
82 Lc.head=new LNode();
83 LNode *pc = Lc.head;
84 while(pa!=La.head&&pb!=Lb.head){
85 if(pa->data < pb->data){
86 pc->next = pa;
87 pa = pa->next;
88 }
89 else{
90 pc->next = pb;
91 pb = pb->next;
92 }
93 pc = pc -> next;
94 }
95 if(pa==La.head){
96 pc->next = pb;
97 while(pb->next!=Lb.head)pb=pb->next;
98 pb->next=Lc.head;
99 }
100 else {
101 pc->next = pa;
102 while(pa->next!=La.head)pa=pa->next;
103 pa->next=Lc.head;
104 }
105
106 }
107 void visit(LNode *p){
108 printf("%d\n",p->data);
109 }
110 int main(){
111 LinkList list,list2,list3 ;
112 // InitList(list);
113 CreateList(list,5);
114 //CreateList(list2,5);
115
116 //MergeList(list,list2,list3);
117 int v =123;
118 //ListDelete_L(list,5,v);
119 //
120 //
121 GetElem_L(list,4,v);
122 printf("%d",v);
123 ListTraverse(list,visit);
124 return 0;
125 }
循環連結清單:
1 #include <cstdio>
2 using namespace std;
3 struct Node{
4 int data;
5 struct Node * prev;
6 struct Node * next;
7 };
8 struct LinkList{
9 Node * head;
10 int len;
11 };
12 void CreateList_L(LinkList &L, int n){
13 L.len = n;
14 L.head = new Node();
15 Node * head = L.head;
16 head->next = NULL;
17 head->prev = NULL;
18 while(n--){
19 Node *t = new Node();
20 scanf("%d",&t->data);
21 Node * d = head->next;
22 t->prev = head;
23 head->next = t;
24 t->next = d;
25 if(d) d->prev = t;
26 }
27 }
28 void CreateList(LinkList &L,int n){
29 L.len = n;
30 L.head = new Node();
31 Node * p = L.head;
32 while(n--){
33 Node *t = new Node();
34 scanf("%d",&t->data);
35 p->next = t;
36 t->prev = p;
37 p = t;
38 }
39 p->next = NULL;
40 }
41 void visit(Node *p){
42 printf("%d",p->data);
43 }
44 void ListTraverse(LinkList L,void (visit)(Node*)){
45 Node *p = L.head->next;
46 while(p->next!=NULL){
47 visit(p);
48 p = p->next;
49 }
50 visit(p);
51 printf("\n");
52 while(p->prev!=NULL){
53 visit(p);
54 p = p->prev;
55 }
56 }
57 int ListInsert_L(LinkList &L,int i ,int data){
58 Node * p = L.head;
59 int j = 0;
60 while(p&&j++ < i)p = p->next;
61 if(!p||i<0)return 0;
62 Node * t = new Node();
63 t->data = data;
64 Node * n = p->next;
65 p->next = t;
66 t->prev = p;
67 if(n)n->prev = t;
68 t->next = n;
69 return 1;
70 }
71 int ListDelete_L(LinkList &L,int i,int &data){
72 Node * p = L.head;
73 int j = 0;
74 while(p && j++ < i) p = p->next;
75 if((!p||!p->next) || i < 0) return 0;
76 Node * n = p->next;
77 data = n->data;
78 if(n->next)n->next->prev = p;
79 p->next = n->next;
80 delete n;
81 return 1;
82 }
83 void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){
84 Node * pa = La.head->next;
85 Node * pb = Lb.head->next;
86 Lc.head = new Node();
87 Node * pc = Lc.head;
88 pc->prev = NULL;
89 while(pa && pc){
90 if(pa->data < pb->data){
91 pc->next = pa;
92 pc->next->prev = pc;
93 pa = pa->next;
94 }
95 else{
96 pc->next = pb;
97 pc->next->prev = pc;
98 pb = pb->next;
99 }
100 pc = pc->next;
101 }
102 if(pa) {
103 pc->next = pa;
104 pa->prev = pc;
105 }
106 else{
107 pc->next = pb;
108 pb->prev = pc;
109 }
110 }
111 int GetElem_L(LinkList L,int i,int &data){
112 Node * p = L.head->next;
113 int j = 0;
114 while(p && j++ < i) p = p->next;
115 if(!p || i < 0)return 0;
116 data = p->data;
117 return data;
118 }
119 int main(){
120 LinkList list,list1,list2;
121 CreateList(list,5);
122 CreateList(list1,5);
123 MergeList(list,list1,list2);
124 //printf("[%d]",v);
125 ListTraverse(list2,visit);
126 return 0;
127 }