链表练习

  1 #include <iostream>
  2 #include <string.h>
  3 using namespace std;
  4 // 定义单链表
  5 struct List
  6 {
  7 
  8     int data;
  9     string name;
 10     List *next;
 11 };
 12 // 此函数用于顺序法插入链表
 13 void Listinsert(List *&L, int num, string id)
 14 {
 15     /* 创建指针 */
 16     List *s, *p, *q;
 17     /* 创建一个节点 */
 18     s = new List;
 19     s->data = num;
 20     s->name = id;
 21     s->next = NULL;
 22     /* 判断此节点是否应放在头节点 */
 23     if (L->data > s->data)
 24     { /* 插入新节点 */
 25         s->next = L;
 26         L = s;
 27         return;
 28     }
 29     /* 循环查找新节点的位置 */
 30     for (q = L, p = L->next; p; q = p, p = p->next)
 31         /* 若不是头节点，则进行判断其位置 */
 32         if (p->data > s->data)
 33         { /* 插入新节点 */
 34             s->next = p;
 35             q->next = s;
 36             return;
 37         }
 38     /* 若其位置在最后。 */
 39     q->next = s;
 40     return;
 41 }
 42 /* 插入法生成有序链表 */
 43 void insert(List *&head, int num, string id)
 44 {
 45     /* 创建指针 */
 46     List *s, *p, *q;
 47     /* 创建一个节点 ，存贮数据*/
 48     s = new List;
 49     s->data = num;
 50     s->name = id;
 51     s->next = NULL;
 52     /* 判断是否生成链表，若无链表则进行创建 */
 53     if (head == NULL)
 54     {
 55         head = s;
 56         return;
 57     }
 58     /* 有链表，则进行判断，查找其应存放位置 */
 59     Listinsert(head, num, id);
 60     return;
 61 }
 62 /* 输出链表 */
 63 void ShowList(const List *head)
 64 {
 65     /* 输出头节点 */
 66     cout << "(" << head->data << "," << head->name << ")";
 67     head = head->next;
 68     while (head)
 69     { /* 循环输出链表 */
 70         cout << "   ->    ";
 71         cout << "(" << head->data << "," << head->name << ")";
 72         head = head->next;
 73     }
 74     /* 结束换行 */
 75     cout << endl;
 76 }
 77 /* 此函数用于删除一个节点 */
 78 void Delete(List *&L, int key)
 79 { /* 创建指针 */
 80     List *p;
 81     /* 判断是否为头节点 */
 82     if (L->data == key)
 83     { /* 为头节点，进行删除 */
 84         p = L;
 85         L = L->next;
 86         delete p;
 87         p = NULL;
 88         return;
 89     }
 90     /* 若不是头节点，则判断是否为以后的节点 */
 91     for (List *pg = L; pg->next; pg = pg->next)
 92     {
 93         if (pg->next->data == key)
 94         { /* 找到节点，进行空间释放 */
 95             p = pg->next;
 96             pg->next = p->next;
 97             delete p;
 98             p = NULL;
 99             /* 操作成功输出提示 */
100             cout << key << "have been deleted" << endl;
101             return;
102         }
103     }
104     /* 未找到此节点，输出提示 */
105     cout << "there is not key:" << key << endl;
106     return;
107 }
108 /* 清除链表 */
109 void dleleteall(List *&L)
110 {
111     /* 创建指针 */
112     List *p = L, *q;
113     while (p != NULL) /* 判断是否操作完毕 */
114     {                 /* 释放一个节点 */
115         q = p;
116         p = p->next;
117         free(q);
118     }
119 }
120 int main()
121 {
122     /* 定义变量 */
123     int k;
124     string Id;
125     List *head = NULL;
126     /* 输出提示，输入数据 */
127     cout << "Enter data to begin, number 0 to end" << endl;
128     cin >> k;
129     if (k != 0)
130     {
131         while (k != 0) /* 判断是否结束 */
132         {              /* 输入数据，调用函数，生成链表 */
133             cin >> Id;
134             insert(head, k, Id);
135             cin >> k;
136         }
137         /* 输出链表 */
138         ShowList(head);
139 
140         /* 输出提示，输入数据 */
141         cout << "Please input a node to add:" << endl;
142         cin >> k;
143         cin >> Id;
144         /* 调用函数，插入链表 */
145         Listinsert(head, k, Id);
146         ShowList(head); /* 输出链表 */
147 
148         /* 输出提示，输入数据 */
149         cout << "Please input a node to delete:" << endl;
150         cin >> k;
151         /* 删除节点 */
152         Delete(head, k);
153         ShowList(head); /* 输出链表 */
154 
155         /* 调用函数，释放链表 */
156         dleleteall(head);
157         /* 程序结束 */
158     }
159     return 0;
160 }

1         while (cin >> k) /* 判断是否结束 */
2         {              /* 输入数据，调用函数，生成链表 */
3             cin >> Id;
4             insert(head, k, Id);
5         }
6         /* 输出链表 */
7         ShowList(head);