왕도 데이터 구조 - 선형 표 에서 링크 의 실현 과 응용

46513 단어
1. 싱글 체인 시트
  1 #include 
  2 #include  
  3 typedef struct LNode{
  4     int data;
  5     struct LNode *next;
  6 }LNode, *LinkList;//            
  7 
  8 /*      */
  9 int LocateElem(LinkList &L, int x){
 10     LNode *p = L -> next;
 11     int cnt = 1;
 12     while(p){
 13         if(p -> data == x)
 14             break;
 15         cnt++;
 16         p = p -> next;
 17     }
 18     return cnt;
 19 } 
 20 /*        ,   0  */
 21 LNode *GetElem(LinkList &L, int i){
 22     LNode *p = L -> next;
 23     if(i == 0) return L;
 24     if(i < 1)  return NULL;
 25     
 26     int cnt = 1;
 27     while(p != NULL){
 28         if(cnt == i)
 29             break;
 30         cnt++;//        ,     1  
 31         p = p->next;
 32     } 
 33     return p;
 34 } 
 35 /* 36  37 */
 38 LinkList CreatList2(LinkList &L){
 39     L = (LinkList)malloc(sizeof(LNode));
 40     L -> next = NULL;
 41     LNode *s, *r = L;
 42     for(int i = 0; i < 7; i++){
 43         s = (LNode*)malloc(sizeof(LNode));
 44         s->data = i;
 45         
 46         r -> next = s;//   s      ,r        
 47         r = s;
 48     }  
 49     r -> next = NULL;//                 
 50     return L; 
 51 }
 52 /*        */
 53 LinkList CreatList1(LinkList &L){
 54     LNode *s;
 55     L = (LinkList)malloc(sizeof(LNode));//      
 56     L->next = NULL;//    
 57     
 58     for(int i = 0; i < 7; i++){
 59         s = (LNode*)malloc(sizeof(LNode));
 60         s->data = i;
 61         
 62         s->next = L->next;//  L next  s   ,       
 63         L -> next = s;
 64     } 
 65     return L; 
 66 }
 67 /*      */
 68 void PrintList(LinkList &L){
 69     LNode *p = L->next;
 70     while(p != NULL){
 71         printf("%d ", p -> data);
 72         p = p->next;
 73     }
 74     puts("");
 75 }
 76 /*       */
 77 int Length(LinkList &L){
 78     LNode *p = L -> next;
 79     int cnt = 0;
 80     while(p != NULL){
 81         cnt++;
 82         p = p-> next;
 83     }
 84     return cnt;
 85 }
 86 /*      , s    i    ,      */
 87 void Insert(LinkList &L, LNode *s, int i){
 88     int Llength = Length(L); 
 89     if(i < 0 || i > Llength)
 90         return;
 91     
 92     LNode *pre = GetElem(L, i - 1);
 93     s -> next = pre -> next;
 94     pre -> next = s;
 95 } 
 96 /*      , s    i     */
 97 void BackInsert(LinkList &L, LNode *s, int i){
 98     int Llength = Length(L); 
 99     printf("   %d
", Llength); 100 if(i < 0 || i > Llength) 101 return; 102 103 LNode *p = GetElem(L, i);// i , , , 104 s -> next = p -> next; 105 p -> next = s; 106 107 /*int temp = p->data; 108 p -> data = s -> data; 109 s -> data = temp;*/ 110 } 111 /* i */ 112 bool DelateElem(LinkList &L, int i){ 113 LNode *pre = GetElem(L, i - 1); 114 LNode *p = pre -> next;// p, 115 pre -> next = p->next; 116 free(p); 117 } 118 int main(){ 119 LinkList L1; 120 CreatList1(L1); 121 PrintList(L1); 122 printf(" :%d
",Length(L1)); 123 124 LinkList L2; 125 CreatList2(L2); 126 PrintList(L2); 127 printf(" :%d
",Length(L2)); 128 129 LNode *x; 130 for(int i = 1; i < 7; i++){ 131 x = GetElem(L2, i); 132 printf(" %d %d
",i, x->data); 133 } 134 for(int i = 2; i < 7; i++){ 135 printf(" %d , %d
",i, LocateElem(L2, i)); 136 } 137 138 LNode *s = (LNode*)malloc(sizeof(LNode)); 139 s -> data = 99; 140 s -> next = NULL; 141 Insert(L2, s, 2); 142 PrintList(L2); 143 144 LNode *s1 = (LNode*)malloc(sizeof(LNode)); 145 s1 -> data = 99; 146 s1 -> next = NULL; 147 // s , , 148 BackInsert(L2, s1, 3);// 149 PrintList(L2); 150 151 DelateElem(L2, 2); 152 DelateElem(L2, 3); 153 PrintList(L2); 154 return 0; 155 }

2. 더 블 링크
  1 #include 
  2 #include  
  3 
  4 typedef struct LNode{
  5     int data;
  6     struct LNode *prior, *next;
  7 }LNode, *LinkList;//           
  8 
  9 /*   */ 
 10 LinkList InitList(LinkList &L){
 11     L = (LinkList)malloc(sizeof(LNode));
 12     L->data = -1;
 13     L->next = NULL;
 14     L->prior = NULL;
 15     return L; 
 16 } 
 17 /*        */
 18 LinkList FrontList(LinkList &L){
 19     L = InitList(L);
 20     
 21     LNode *s;
 22     for(int i = 0; i < 7; i++){
 23         s = (LNode*)malloc(sizeof(LNode));//         
 24         s->data = i;
 25         
 26         s->next = L->next;
 27         L->next = s;
 28         s->prior = L;
 29         if(s->next != NULL)
 30             s->next->prior = s;
 31     }
 32     return L;
 33 }
 34 /*        */
 35 LinkList BackList(LinkList &L){
 36     L = InitList(L);
 37     LNode *s, *r = L;
 38     
 39     for(int i = 0; i < 7; i++){
 40         s = (LNode*)malloc(sizeof(LNode));//         
 41         s->data = i;
 42         
 43         r->next = s;
 44         s->prior = r;
 45         r = s;
 46     }
 47     r -> next = NULL;
 48     return L;
 49 }
 50 /*   */
 51 int Length(LinkList &L){
 52     LNode *p = L -> next;
 53     int cnt = 0;
 54     while(p){
 55         cnt++;
 56         p = p->next;
 57     }
 58     //L->data = cnt;
 59     return cnt;
 60 }
 61 /*      */
 62 LNode *GetElem(LinkList &L, LNode *e){
 63     LNode *p = L->next;
 64     while(p && p->data != e->data){
 65         p = p->next;
 66     } 
 67     return p;
 68 }
 69 /*       , 1  */
 70 LNode *LocateElem(LinkList &L, int x){
 71     int Llength = Length(L);
 72     if(x < 0 || x > Llength)
 73         return NULL;
 74     
 75     LNode *p = L->next;
 76     int cnt = 0;
 77     while(p && cnt < x){
 78         cnt++;
 79         p = p->next;
 80     } 
 81     return p;
 82 }
 83 /*  , i   */
 84 bool ListInsert(LinkList &L, LNode *s, int i){
 85     int Llength = Length(L);
 86     if(i < 0 ||i >= Llength)
 87         return false;
 88         
 89     LNode *p = LocateElem(L, i - 1);
 90     s->next = p->next;
 91     p->next = s;
 92     s->next->prior = s;
 93     s->prior = p;
 94 }
 95 /*  */
 96 bool ListDelate(LinkList &L, int i, LNode &e){
 97     int Llength = Length(L);
 98     if(i < 0 ||i >= Llength)
 99         return false;
100         
101     LNode *q, *p = LocateElem(L, i - 1);
102     q = p -> next;
103     e.data = q -> data;
104     
105     p->next = q->next;
106     q->next->prior = p;
107     free(q);//     i         
108 }
109 /*  */
110 void PrintList(LinkList &L){
111     printf("");
112     LNode *p = L; 
113     LNode *p1 = NULL;
114     while(p != NULL){
115         printf("%d ", p->data);
116         if(p->next == NULL)
117             p1 = p;
118         p = p -> next;
119     }
120     puts(""); 
121     
122     printf("");
123     while(p1){
124         printf("%d ", p1->data);
125         p1 = p1 -> prior;
126     }
127     puts("");
128 }
129 /*  */
130 bool Empty(LinkList &L){
131     if(L->next == NULL)
132         return true;
133     return false;
134 }
135 /*  ,      */ 
136 void Destory(LinkList &L, LNode *s){
137     if(s == NULL){
138         L->next = NULL;
139         return;
140     }
141         
142     Destory(L,s->next);
143     free(s);
144     s=NULL;
145     //L->data--;
146 } 
147 /*  ,       */ 
148 void Destory2(LinkList &L){
149     LNode *t,*p = L -> next;
150     while(p){
151         t = p -> next;
152         free(p);
153         L->data--;
154         p = t;
155     }
156     L -> next = NULL;
157 } 
158 
159 int main()
160 {
161     LinkList L2 = BackList(L2);
162     PrintList(L2);
163     printf("      %d
", Length(L2)); 164 165 LinkList L = FrontList(L); 166 PrintList(L); 167 printf(" %d
", Length(L)); 168 169 Destory(L2, L2->next); 170 PrintList(L2); 171 if(Empty(L2)) 172 printf("
"); 173 174 /*Destory2(L); 175 PrintList(L); 176 if(Empty(L)) 177 printf("
");
*/ 178 179 PrintList(L); 180 LNode *x = (LNode*)malloc(sizeof(LNode)); 181 x -> data = 3; 182 x -> next = x ->prior = NULL; 183 printf(" %d
", GetElem(L, x)->data); 184 for(int i = 0; i < 4; i++) 185 printf(" %d %d
",i, LocateElem(L, i)->data); 186 187 x -> data = 99; 188 ListInsert(L, x, 3); 189 PrintList(L); 190 191 LNode e; 192 e.data = -1; 193 e.next = e.prior = NULL; 194 ListDelate(L, 3, e); 195 printf(" %d
", e.data); 196 PrintList(L); 197 198 return 0; 199 }

좋은 웹페이지 즐겨찾기