【数据结构与算法】第三章表c实现

表是一种常用的数据结构，它支持的基本操作有插入和删除。最基本地可以用数组来实现表结构，但因为数组中的数据都是连续存储的，若动态指定数组，会造成空间的浪费。而且在有序插入删除操作时，都需要调整元素在数组中的位置，因此，一般不使用数组来实现表结构。一般来说，使用链表来实现表结构。下面的程序中写了16个常用的链表函数，它源于http://www.bccn.net/Article/kfyy/cjj/jszl/200708/5227_2.html这篇文档，但上述文档中实现的是一个无表头的线性表结构。本文中对上述程序稍作修改，实现了一个有表头的链表结构。具体代码如下：

  1 /*
  2  * linear list implemention in c
  3  * with head
  4  * author: qiqi
  5  */
  6 
  7 #include <stdio.h>
  8 #include <stdlib.h>
  9 
 10  #define NN 12
 11  #define MM 20
 12 
 13 typedef int ElementType;
 14 
 15  /*
 16  * Node struct
 17  */
 18 typedef struct _Node
 19 {
 20     ElementType element;
 21     struct _Node* next;
 22 }Node;
 23 typedef Node * List;
 24 
 25  //1: 初始化线性表，即置单链表的表头指针为空
 26  void
 27 initList( List *hl )
 28 {
 29     *hl = ( Node * )malloc( sizeof( Node ) );
 30     if( *hl == NULL )
 31       perror( "Out of space!!!\n" );
 32     (*hl)->element = 0;
 33     (*hl)->next = NULL;
 34     return;
 35 }
 36 
 37  //2: 清除线性表中所有元素，释放L中的所有结点，使之成为一个空表
 38  void emptyList( List *hl )
 39 {
 40     //cp 和 np分别为指向相邻结点的指针
 41      Node *cp, *np;
 42     cp = (*hl)->next;
 43     while( cp != NULL )
 44     {
 45         np = cp->next;
 46         free( cp );
 47         cp = np;
 48     }
 49     //表头next元素置空
 50      (*hl)->next = NULL;
 51     return;
 52 }
 53 
 54  //3: 返回单链表的长度
 55  int sizeList( List hl )
 56 {
 57     int count = 0;
 58     hl = hl->next;
 59     while ( hl != NULL )
 60     {
 61         count++;
 62         hl = hl->next;
 63     }
 64     return count;
 65 }
 66 
 67  //4: 检查单链表是否为空，若为空，则返回1，否则返回0
 68  int isEmpty( List hl )
 69 {
 70     return hl->next == NULL;
 71 }
 72 
 73  //5: 返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序进行
 74 ElementType getElement( List hl, int pos )
 75 {
 76     int i = 0;
 77     hl = hl->next;
 78     if( pos < 1 )
 79     {
 80         printf("pos is not legal, quit!\n");
 81         exit(1);
 82     }
 83     while( hl != NULL )
 84     {
 85         i++;
 86         if( i == pos )
 87           break;
 88         else
 89           hl = hl->next;
 90     }
 91     if( hl != NULL )
 92       return hl->element;
 93     else
 94     {
 95         printf("pos is not legal, quit!\n");
 96         exit(1);
 97     }
 98 }
 99 
100 //6: 打印一个链表
101 void printList( List hl )
102 {
103     hl = hl->next;
104     while( hl != NULL )
105     {
106         printf("%5d", hl->element);
107         hl = hl->next;
108     }
109     printf("\n");
110     return;
111 }
112 
113 //7: 在单链表中查找出现给定值x的第一个元素的位置
114 //若成功，则返回该结点data域的存储地址
115 //否则，返回NULL
116 ElementType* findList( List hl, ElementType x )
117 {
118     hl = hl->next;
119     while( hl != NULL )
120     {
121         if( hl->element == x )
122           return &(hl->element);
123         else
124           hl = hl->next;
125     }
126     return NULL;
127 }
128 
129 //8: 把单链表中pos结点处的值修改为x的值
130 //若修改成功返回1，否则返回0
131 int updateList( List hl, int pos, ElementType x )
132 {
133     int i = 0;
134     Node * cp;
135     cp = hl->next;
136     while( cp != NULL )
137     {
138         i++;
139         if( pos == i )
140           break;
141         else
142           cp = cp->next;
143     }
144     if( pos == i )
145     {
146         cp->element = x;
147         return 1;
148     }
149     else
150       return 0;
151 }
152 
153 //9: 向单链表的表头插入一个元素
154 void insertFirstList( List *hl, ElementType x )
155 {
156     Node * newCell;
157     newCell = ( Node * )malloc( sizeof( Node ) );
158     if( newCell == NULL )
159     {
160         perror("Out of space!!!\n");
161         exit(1);
162     }
163 
164     newCell->element = x;
165     newCell->next = (*hl)->next;
166     (*hl)->next = newCell;
167     return;
168 }
169 
170 //10: 向单链表的末尾添加一个元素
171 void insertLastList( List *hl, ElementType x )
172 {
173     Node * newCell;
174     Node * cp;
175     newCell = ( Node * )malloc( sizeof( Node ) );
176     if( newCell == NULL )
177     {
178         perror("Out of space!!!\n");
179         exit(1);
180     }
181 
182     newCell->element = x;
183     newCell->next = NULL;
184 
185     cp = (*hl)->next;
186     while( cp != NULL )
187       cp = cp->next;
188     cp->next = newCell;
189     return;
190 }

  1 //11: 向单链表pos个结点处插入元素为x的结点
  2 //若成功，返回1，否则，返回0
  3 int insertPosList( List *hl, int pos, ElementType x )
  4 {
  5     Node * newCell;
  6     Node *cp, *pp;
  7     int i = 0;
  8 
  9     //还应该判断pos是不是超出链表的长度
 10     if( pos <= 0 )
 11     {
 12         perror("pos is not legal, quit!\n");
 13         exit(1);
 14     }
 15 
 16     cp = (*hl)->next;
 17     while( cp != NULL )
 18     {
 19         i++;
 20         if( pos == i )
 21           break;
 22         else
 23         {
 24             //pp 为Pos前一个位置处
 25             //cp 为pos位置处
 26             pp = cp;
 27             cp = cp->next;
 28         }
 29     }
 30 
 31     newCell = ( Node * )malloc( sizeof( Node ) );
 32     if( newCell == NULL )
 33     {
 34         perror( "Out of space!!!\n");
 35         return 0;
 36     }
 37     newCell->element = x;
 38     
 39     if( pos == i )
 40     {
 41         newCell->next = cp;
 42         pp->next = newCell;
 43     }
 44     else
 45     {
 46         perror("pos is not legal, quit\n");
 47         return 0;
 48     }
 49     return 1;
 50 }
 51 
 52 //12: 向有序单链表中插入元素x结点，使得插入后仍然有序
 53 void insertOrderList( List *hl, ElementType x )
 54 {
 55     Node *cp, *pp;
 56     Node *newCell;
 57     cp = (*hl)->next;
 58     pp = NULL;
 59     newCell = ( Node * )malloc( sizeof( Node ) );
 60     if( newCell == NULL )
 61     {
 62         perror("Out of space!!!\n");
 63         exit(1);
 64     }
 65     newCell->element = x;
 66 
 67     //将新的结点插入到1的位置,即表头元素之后
 68     if( cp == NULL || x < cp->element)
 69     {
 70         newCell->next = cp;
 71         (*hl)->next = newCell;
 72         return;
 73     }
 74     while( cp != NULL )
 75     {
 76         if( x < cp->element )
 77           break;
 78         else
 79         {
 80             pp = cp;
 81             cp = cp->next;
 82         }
 83     }
 84 
 85 
 86     newCell->next = cp;
 87     pp->next = newCell;
 88     return;
 89 }
 90 
 91 //13: 删除单链表中第一个元素，并把该结点值返回
 92 ElementType deleteFirstList( List *hl )
 93 {
 94     ElementType temp;
 95     Node * cp = (*hl)->next;
 96     if( cp == NULL )
 97     {
 98         printf("单链表为空，没有元素\n");
 99         exit(1);
100     }
101 
102     (*hl)->next = cp->next;
103     temp = cp->element;
104     free(cp);
105     return temp;
106 }
107 
108 //14: 从单链表中删除尾部结点，并返回该结点值
109 ElementType deleteLastList( List *hl )
110 {
111     ElementType temp;
112     Node *cp, *pp;
113     cp = (*hl)->next;
114     pp = NULL;
115 
116     if( cp == NULL )
117     {
118         printf("单链表为空，没有元素可删除.\n");
119         exit(1);
120     }
121 
122     while( cp->next != NULL )
123     {
124         pp = cp;
125         cp = cp->next;
126     }
127 
128     //若单链表中只有一个结点
129     if( pp == NULL )
130     {
131         (*hl)->next = cp->next;
132     }
133     else
134     {
135         pp->next = NULL;
136     }
137 
138     temp = cp->element;
139     free(cp);
140     return temp;
141 }
142 
143 //15: 从单链表中删除第pos个结点，并返回其值
144 ElementType deletePosList( List *hl, int pos )
145 {
146     int i = 0;
147     ElementType temp;
148     Node *cp, *pp;
149 
150     cp = (*hl)->next;
151     pp = NULL;
152 
153     if( ( cp == NULL ) || ( pos <= 0 ) )
154     {
155         printf("单链表为空或pos值不正确，退出运行.\n");
156         exit(1);
157     }
158 
159     //单链表中找出pos个结点，找到后cp指向该结点，pp指向其前驱结点
160     while( cp != NULL )
161     {
162         i++;
163         if( i == pos )
164           break;
165         else
166         {
167             pp = cp;
168             cp = cp->next;
169         }
170     }
171 
172     //单链表中没有pos结点
173     if( cp == NULL )
174     {
175         printf("pos值不正确\n");
176         exit(1);
177     }
178     //若pos=1，需要删除第一个结点
179     if( pos == 1 )
180       (*hl)->next = cp->next;
181     else
182       pp->next = cp->next;
183 
184     temp = cp->element;
185     free(cp);
186     return temp;
187 }
188 
189 //16: 从单链表中删除值为x的第一个结点
190 //成功返回1，否则返回0
191 int deleteValueList( List *hl, ElementType x )
192 {
193     Node *pp, *cp;
194     cp = (*hl)->next;
195     pp = NULL;
196 
197     while( cp != NULL )
198     {
199         if( cp->element == x )
200           break;
201         else
202         {
203             pp = cp;
204             cp = cp->next;
205         }
206     }
207 
208     //查找失败
209     if( cp == NULL )
210       return 0;
211     //如果删除的是表头元素
212     if( pp == NULL )
213       (*hl)->next = cp->next;
214     else
215       pp->next = cp->next;
216 
217     free(cp);
218     return 1;
219 }
220 
221 /***********************************************
222  ***********************************************/
223 int main( int argc, char* argv[] )
224 {
225     int a[NN];
226     int i;
227     Node *p, *h, *s;
228     srand( time( NULL ) );
229     initList( &p );
230     for( i = 0; i < NN; i++ )
231       a[i] = rand() & MM;
232 
233     printf("随机数序列： ");
234     for( i = 0; i < NN; i++ )
235       printf("%5d", a[i]);
236     printf("\n");
237 
238     printf("随机数逆序: ");
239     for( i = 0; i < NN; i++ )
240       insertFirstList( &p, a[i] );
241     printList( p );
242     
243     printf("单链表长度: %5d\n", sizeList( p ) );
244 
245     //删除链表元素测试
246     //p指向生成的逆序数列
247     for( h = p; h->next != NULL; h = h->next )
248     {
249         while( deleteValueList( &(h->next), (h->next)->element ) )
250         {
251             ;
252         }
253     }
254     printf("删除链表元素: ");
255     printList( p );
256     printf("单链表长度: %5d\n", sizeList( p ) );
257     
258     h = NULL;
259     initList( &h );
260     for( s = p->next; s != NULL; s = s->next )
261     {
262         insertOrderList( &h, s->element );
263     }
264     printf("有序表序列: ");
265     printList( h );
266     emptyList( &h );
267     return 0;
268 }

编程序时，值得注意的几点：

1、typedef定义结构体时:

typedef int Element;
typedef struct _Node
{
     ElementType element;
     struct _Node * next;
}Node;

此时Node是结构体地名称，我们可以用Node a;来定义一个Node类型的变量a，也可以用Node *pn;来定义一个指向Node类型变量的指针。上述的例子中，_Node是一个记号，当需要定义的结构体中包含一个指针，而这个指针类型为指向定义的结构体变量，那么这时候需要记号的辅助作用。

2、函数的参数类型应该注意，若需要改变传入的变量值，则需用指针或引用参数。如果不修改参数内容，则只需用值参数。

3、对指针、引用、函数参数这几点的理解还不到位，需要继续吃透。

【数据结构与算法】第三章 表c实现

【数据结构与算法】第三章表c实现