データ構造-シングルチェーン表の基本操作の実現(すべてのコードを含む)

著作権声明:本文はブロガーオリジナル文章で、CC 4.0 BY-SA著作権契約に従い、転載は原文の出所リンクと本声明を添付してください.本論文のリンク:https://blog.csdn.net/lady_killer 9/articale/detail/82700723
 
今日はシングルチェーン表の実現です.主な実現関数は以下の通りです.

    InitList(Link List&L)               パラメータ:シングルチェーンテーブルL機能:初期化時間複雑度O(1)

    ListLength(LinkList L)           パラメータ:シングルチェーンテーブルL機能:シングルチェーンテーブル長時間複雑度O(n)

を得る.

    ListInsertパラメータ:シングルチェーンテーブルL、位置i、要素e機能:位置iポストタイム複雑度O(n)［検索に追加しました］

                                                                        ポインタpが指すことが知られている場合は、O(1)

を挿し込む.

    ListDelete(LinkList&L,int i)パラメータ:シングルチェーンテーブルL、位置i機能:位置i要素を削除する時間複雑度O(n)［検索に追加しました］

                                                    pポインタが指定されていると知っている場合は、O(1)が一番いいです.データドメインは後のノードと交換して、後のノードを削除します.

                                                    最悪はO(n)で、つまりpの前の結点を最初から検索し、pの指す結点

を削除する.

    LocateElem(LinkList L,ElemType)パラメータ:シングルチェーンテーブルL,要素e機能:最初のeに等しい要素を探して、ポインタ時間複雑度O(n)

を返します.
 
 
コード:

  1 /*
  2     Project: single linkeed list (        )
  3     Date:    2018/09/14
  4     Author:  Frank Yu
  5     InitList(LinkList &L)   ：   L   ：          O(1)
  6     ListLength(LinkList L)   ：   L   ：             O(n) 
  7     ListInsert(LinkList &L,int i,ElemType e)   ：   L,  i，  e   ：  i        O(n)[     ]
  8                                                  p      O(1)
  9     ListDelete(LinkList &L,int i)   ：   L，  i   ：    i        O(n)[     ] 
 10                                      p           O(1),              ，        。
 11                                      O(n),     p     ,    p    
 12     LocateElem(LinkList L,ElemType e)   ：   L，  e   ：       e   ，          O(n) 
 13 */
 14 #include
 15 #include
 16 #include
 17 #include
 18 #include
 19 using namespace std;
 20 #define Status int
 21 #define ElemType int
 22 //         
 23 typedef struct LNode
 24 {
 25     ElemType data;//   
 26     struct LNode *next;//   
 27 }LNode,*LinkList;
 28 //**************************      ***************************//
 29 //     
 30 Status InitList(LinkList &L)
 31 {
 32  L = new LNode;//                          
 33  L->next = NULL;
 34  return 1;
 35 }
 36 //              ，  
 37 int ListLength(LinkList L)
 38 {
 39     LinkList p=L;int sum=0;
 40     while(p)
 41     {
 42      sum++;
 43      p=p->next;
 44     }
 45     return sum-1;//     
 46 }
 47 //    --        i(1<=i<=length+1)     i-1       i   
 48 bool ListInsert(LinkList &L,int i,ElemType e)
 49 {
 50     LNode* s;LinkList p=L;int j=0;
 51     while(p&&(j1))//j  i-1  
 52     {
 53      p=p->next;
 54      ++j;
 55     }
 56     if(!p||j>i-1)//i<1  i>ListLength(L)+1 ,          ListLength,    
 57     {
 58         printf("      ！！！
");
 59         return false;
 60     }
 61     s=new LNode;
 62     s->data=e;
 63     s->next=p->next;
 64     p->next=s;
 65     return true;
 66 }
 67 //         i       i-1     
 68 bool ListDelete(LinkList &L,int i)
 69 {
 70      LNode* s;LinkList p=L;int j=0;
 71     LinkList q;
 72     while(p&&(j1))//j  i-1  
 73     {
 74      p=p->next;
 75      ++j;
 76     }
 77     if(!(p->next)||j>i-1)//i<1  i>ListLength(L) ,      
 78     {
 79         printf("      ！！！
");
 80         return false;
 81     }
 82     q=p->next;
 83     p->next=q->next;
 84     free(q);//    
 85     return true;
 86 }
 87 //                 e             ，    NULL
 88 LNode *LocateElem(LinkList L,ElemType e)
 89 {
 90     LNode *p=L;
 91     while(p&&(p->data!=e))
 92     {
 93         p=p->next;
 94     }
 95     return p;
 96 }
 97 //**************************      **************************//
 98 //      
 99 void PrintList(LinkList L)
100 {
101     LinkList p=L->next;//     
102     if(ListLength(L))
103     {
104         printf("         :");
105         while(p)
106         {
107             printf("%d ",p->data);
108             p=p->next;
109         }
110         printf("
");
111     }
112     else
113     {
114         printf("       ！
");
115     }
116 }
117 //         ListInsert  
118 void Insert(LinkList &L)
119 {
120   int place;ElemType e;bool flag;
121   printf("         ( 1  )   :
");
122   scanf("%d%d",&place,&e);
123   flag=ListInsert(L,place,e);
124   if(flag) 
125   {
126     printf("    ！！！
");
127     PrintList(L);
128   }
129 }
130 //         ListDelete  
131 void Delete(LinkList L)
132 {
133   int place;bool flag;
134   printf("         ( 1  ):
");
135   scanf("%d",&place);
136   flag=ListDelete(L,place);
137   if(flag) 
138   {
139     printf("    ！！！
");
140     PrintList(L);
141   }
142 }
143 //         LocateElem  
144 void Search(LinkList L)
145 {
146   ElemType e;LNode *q;
147   printf("        :
");
148   scanf("%d",&e);
149   q=LocateElem(L,e);
150   if(q) 
151   {
152     printf("     ！
");
153   }
154   else
155     printf("      ！
");
156 }
157 //  
158 void menu()
159 {
160    printf("********1.      2.  *********
");
161    printf("********3.      4.  *********
");
162    printf("********5.            *********
");
163 }
164 //   
165 int main()
166 {
167  LinkList L;int choice;
168  InitList(L);
169  while(1)
170  {
171   menu();
172   printf("       ：
");
173   scanf("%d",&choice);
174   if(choice==5) break;
175   switch(choice)
176   {
177   case 1:Insert(L);break;
178   case 2:Delete(L);break;
179   case 3:Search(L);break;
180   case 4:PrintList(L);break;
181   default:printf("    ！！！
");
182   }
183  }
184  return 0;
185 }