线性表学习笔记

最近学习数据结构的线性表，主要是借助教材《数据结构》（C语言版）那本。在课堂上学习的时候没有认真听讲，唉，，，书上面的程序没有写过，知识了解大概，现在开始准备面试，数据结构是首先要拿下的基础知识，所以开始了数据结构的再学习，下面是线性表部分，下面还会有栈、队列、串、数组、树、图、排序、查找等等。程序不一定完全正确，都是用C语言实现的书上的例子，没有包括所有的线性表性质，但基本上实现了线性表基本操作（顺序和链式），欢迎大家提出宝贵意见。

下面附上练习源码（仅作参考）

  1 /**   2  * 线性表的各种操作   3  * 对应《数据结构(C语言版)》的教材   4  * @author:zhaoyafei   5  * @aime:2015-6-16   6  */   7 //引入必要头文件   8 #include <stdio.h>   9 #include <stdlib.h>  10 //约定的宏定义    11 #define TRUE 1  12 #define FALSE 0  13 #define OK 1  14 #define ERROR 0  15 #define INFEASIBLE -1  16 #define OVERFLOW -2  17   18 //初始空间分配量  19 #define LIST_INIT_SIZE 100  20 //空间分配的增量  21 #define LISTINCREMENT  10  22 //Status是函数的类型，其值是函数结果的状态码  23 typedef int Status;  24 //数据元素约定为ElemType，可以自己定义  25 typedef int ElemType;  26   27 //线性表的顺序实现  28 typedef struct{  29     ElemType * elem;  //存储空间的基地址  30     int      lenght;  //当前的长度  31     int      listsize;//当前分配的存储容量  32 }SqList;  33   34 //线性表的链式实现  35 typedef struct LNode{  36     ElemType     data; //存储数据  37     struct LNode * next; //递归定义，指向下一个元素  38 }LNode,*LinkList;//结构体类型指针  39   40   41 /*************************顺序实现***************************/  42 //构造空的线性表  43 Status InitList(SqList &L, int lenght){  44     if (lenght == 0) {  45         lenght = LIST_INIT_SIZE;  46     }  47     L.elem = (ElemType *)malloc(lenght * sizeof(ElemType));  48   49     if(!L.elem){  50         exit(OVERFLOW);  //分配存储空间失败  51     }  52     L.lenght = 0;        //初始空表长度为0  53     L.listsize = lenght ;//初始存储容量为100  54     return OK;  55 }  56   57 //在第i的位置插入元素e  58 Status ListInse_Sq(SqList &L, ElemType e, int i){  59     ElemType *p, *q;  60     if(i < 0 || i > L.lenght){  61         //i的值不合法  62         return ERROR;  63     }  64     if (L.lenght >= L.listsize) {  65         //空间不够，重新分配存储空间  66         ElemType *newbase = (ElemType *)realloc(L.elem ,(L.listsize + LISTINCREMENT)*sizeof(ElemType));  67         if(!newbase){  68             return OVERFLOW;            //存储分配失败  69         }  70         L.elem = newbase;               //记录新基值  71         L.listsize += LISTINCREMENT;    //增加存储容量  72     }  73     q = &L.elem[i];                     //得到元素插入的位置  74     for (p = &L.elem[L.lenght]; p >= q; --p) {  75         *p = *(p-1);                    //把插入位置元素之后的元素往后移动  76     }  77     *q = e;                             //插入新元素e  78     L.lenght +=1;  79     return OK;  80 }     81   82 //删除第i位置元素，并用e返回其值  83 Status ListDelete_sq(SqList &L, int i, ElemType &e){  84     int *p,*q;  85     if(i < 0 || i > L.lenght){  86         return ERROR;  //i的值不合法  87     }  88     q = &L.elem[i];    //被删除元素的位置为i;  89     e = *q;            //被删除元素的值赋值给e  90     //被删除元素后的元素左移  91     for (p = q; p< (L.elem + L.lenght); p++){    92         *p = *(p + 1);  93     }  94     --L.lenght;  95     return OK;  96 }    97   98 //得到第i个元素  99 Status GetElem(SqList &L, int i, ElemType &e){ 100     ElemType *p; 101     p = L.elem; 102     int j = 1; 103     if(i < 1){ 104         exit(OVERFLOW);//下表不合法 105     } 106     while(p && j < i){ 107         p = &L.elem[j]; 108         j++; //寻找第i个元素，同时检查p是否越界 109     } 110     if(!p || j > i){ 111         return false;//下标越界 112     } 113     e = L.elem[j]; 114     return OK; 115 } 116  117 //打印线性表 118 void PrintList(SqList L){ 119     for(int i = 0; i < L.lenght; i++) { 120         printf("%d ", *(L.elem + i)); 121     } 122     printf("/r/n"); 123 }  124  125 //合并两个线性表 126 void Combine(SqList La, SqList Lb, SqList &Lc){ 127     ElemType *pa, *pb, *pc; 128     Lc.listsize =  La.lenght + Lb.lenght; 129     InitList(Lc, Lc.listsize); //初始化LC/pc = Lc.elem; 130     Lc.lenght = Lc.listsize; 131     pc = Lc.elem; 132     pa = La.elem; 133     pb = Lb.elem; 134     //还没有循环完 135     while (pa <= &La.elem[La.lenght -1] && pb <= &Lb.elem[Lb.lenght -1]){ 136         if (*pa <= *pb){ 137             *pc++ = *pa++; 138         }else{ 139             *pc++ = *pb++; 140         } 141     } 142     //插入La的剩余元素   143     while(pa <= &La.elem[La.lenght -1]){ 144         *pc++ = *pa++; 145     } 146     //插入Lb的剩余元素  147     while(pb <= &Lb.elem[Lb.lenght -1]){ 148         *pc++ = *pb++; 149     } 150 }  151  152 //冒泡排序法，排序线性表 153 void Sort(SqList &L){ 154     ElemType *pd1,*pd2,nums,length = L.lenght; 155     for(int num = 0; num < length - 1; num++){ 156         for(int num1 = num + 1 ;num1 < length; num1++){ 157             pd1 = &L.elem[num]; 158             pd2 = &L.elem[num1]; 159             if(*pd1 > *pd2){ 160                 nums = *pd1; 161                 *pd1 = *pd2; 162                 *pd2 = nums; 163             } 164         } 165     } 166 } 167   168 /*************************链式实现***************************/ 169 //单链表初始化 170 Status InitList_L(LinkList &L){ 171     L = (LinkList)malloc(sizeof(LNode)); 172     if(!L){ 173         exit(OVERFLOW);  //分配存储空间失败 174     } 175     L->next = NULL; //初始的头结点为空 176     return OK; 177 } 178  179 //逆向建立单链表 180 Status CreateList_L(LinkList &L, int n){ 181     L = (LinkList)malloc(sizeof(LNode)); 182     if(!L){ 183         exit(OVERFLOW);  //分配存储空间失败 184     } 185     L->next = NULL; //初始的头结点为空 186     printf("请输入5个整数：/n"); 187     for(int i = n; i > 0; --i){ 188         LinkList p; 189         p = (LinkList)malloc(sizeof(LNode)); 190         scanf("%d",&p->data); 191         p->next = L->next; 192         L->next = p; 193     } 194     return OK; 195 } 196  197 //在建立好的单链表中的第n个位置插入元素e 198 Status ListInsert_L(LinkList &o, int n, ElemType e){ 199     LinkList L = o; 200     int j = 0;//记录插入点的位置 201     while(L && j < n - 1 && n > 0){ 202         L = L->next; 203         j++; 204     } 205     if(L){//合法 206         LinkList p; 207         p = (LinkList)malloc(sizeof(LNode)); 208         p->data = e; 209         p->next = L->next; 210         L->next = p; 211         return OK; 212     } 213 } 214  215 //在建立好的单链表中的第n个位置删除元素，并用e返回 216 Status ListDelete_L(LinkList &o, int n, ElemType e){ 217     LinkList L = o; 218     int j = 0; //记录插入点的位置 219     while(L && j < n - 1 && n > 0){ 220         L = L->next; 221         j++; 222     } 223     if(L && L->next){//合法 224         LinkList q; 225         q = L->next; 226         e = q->data; 227         L->next = q->next; 228         free(q); 229         return OK; 230     } 231 } 232  233 //合并链式线性表 234 void Combine_L(LinkList &La, LinkList &Lb,LinkList &Lc){ 235     LinkList pa,pb,pc; 236     pa = La->next; 237     pb = Lb->next; 238     //Lc = La;//把La作为Lc的头结点 239     pc = Lc; 240     while(pa && pb){ 241         if(pa->data <= pb->data){//判断两者得大小 242             pc->next = pa; 243             pa = pa->next; //pa指针下移 244         }else{ 245             pc->next = pb; 246             pb = pb->next; //pb指针下移 247         } 248         pc = pc->next; //pc下移一位 249     } 250     pc->next = pa ? pa : pb; 251     free(La); 252     free(Lb); 253 } 254  255 //得到第i个元素 256 Status GetElem_L(LinkList &L, int i, ElemType &e){ 257     LinkList p; 258     p = L; 259     int j = 0; 260     if(i < 1){ 261         exit(OVERFLOW);//下表不合法 262     } 263     while(p && j < i){ 264         p = p->next;//寻找第i个元素，同时检查p是否越界 265         j++; 266     } 267     if(!p || j > i){ 268         return false;//下标越界 269     } 270     e = p->data; 271     return OK; 272 } 273  274 //冒泡排序法排序单链表 275 void Sort_L(LinkList &L){ 276     LinkList p,q; 277     int num; 278     for(p = L; p != NULL; p = p->next){ 279         for(q = p->next;q != NULL; q = q->next){ 280             if(p->data > q->data){ 281                 num = p->data; 282                 p->data = q->data; 283                 q->data = num; 284             } 285         } 286     } 287 } 288 //打印链表节点信息 289 void PrintfList_L(LinkList L){ 290     if(L){ 291         do{ 292             L = L->next; 293             printf("%d ",L->data); 294         }while(L->next); 295     } 296     printf("/n"); 297 } 298  299 //主方法 300 void main(){ 301     ElemType e,f; 302     int init,i,elem;     303     int TestData[8] = {9,1,8,5,7,2,1,3}; 304     int TestDataTwo[5] = {8,3,2,6,1}; 305  306     printf("*************线性表顺序实现*************/n"); 307     SqList La,Lb,Lc; 308     init = InitList(La, LIST_INIT_SIZE); 309      310     for (i = 0; i < 8; i++) {//初始化La 311         ListInse_Sq(La, TestData[i], i); 312     } 313     printf("La:/n构造后的La:"); 314     PrintList(La); 315      316     GetElem(La,3,e);//得到第3个元素 317     printf("得到La的第3个元素是:%d/n",e); 318  319     ListDelete_sq(La,3,e);//线性表的删除操作 320     printf("删除后的La:"); 321     PrintList(La); 322  323     ListInse_Sq(La,e,3);//还原数据 324    325     Sort(La);//排序   326     printf("排序后的La:"); 327     PrintList(La); 328  329     printf("Lb:/n构造后的Lb:"); 330     InitList(Lb, LIST_INIT_SIZE); 331     for (i = 0; i < 5; i++) {   332         ListInse_Sq(Lb, TestDataTwo[i], i); 333     } 334     PrintList(Lb); 335  336     Sort(Lb);//排序Lb 337     printf("排序后的Lb:"); 338     PrintList(Lb); 339  340     printf("合并La与Lb后的Lc:");//合并La,Lb 341     Combine(La, Lb, Lc); 342     PrintList(Lc); 343  344     printf("/n*************线性表链式实现*************/n"); 345     LinkList LaL,LbL,LcL,LdL; 346     //CreateList_L(LbL,5)//逆序建立单链表 347     InitList_L(LaL);//初始化单链表 348     printf("LaL:/n构造后的LaL:"); 349     for (i = 1; i <= 8; i++) {//初始化La 350         ListInsert_L(LaL, i, TestData[i-1]); 351     } 352  353     PrintfList_L(LaL);//打印单链表信息 354  355     GetElem_L(LaL,3,e);//得到第3个元素 356     printf("得到LaL的第3个元素是:%d/n",e); 357  358     ListInsert_L(LaL,3,10);//插入新元素 359     printf("插入后的LaL:"); 360     PrintfList_L(LaL); 361      362     ListDelete_L(LaL,3,e);//删除添加的新元素 363     printf("删除后的LaL:"); 364     PrintfList_L(LaL); 365  366     Sort_L(LaL);//排序   367     printf("排序后的LaL:"); 368     PrintfList_L(LaL); 369      370     printf("LbL:/n构造后的LbL:"); 371     InitList_L(LbL);//初始化单链表 372      373     for (i = 1; i < 6; i++) {   374         ListInsert_L(LbL, i, TestDataTwo[i-1]); 375     } 376     PrintfList_L(LbL); 377      378     printf("排序后的LbL:"); 379     Sort_L(LbL);//排序   380     PrintfList_L(LbL); 381  382     printf("合并La与Lb后的Lc:"); 383     InitList_L(LcL);//初始化单链表 384     Combine_L(LaL, LbL, LcL); 385     PrintfList_L(LcL); 386 }

运行结果：

需要补充一下知识点：C语言动态内存分配 ，C动态内存分配主要有这几个函数： malloc、free、calloc、realloc

malloc：原型 void *malloc（unsigned size）

例如：初始化线性表（构造空的线性表 ）

L.elem = (ElemType *)malloc(lenght * sizeof(ElemType));

例如：ElemType *newbase = (ElemType *)realloc(L.elem ,(L.listsize +LISTINCREMENT)*sizeof(ElemType));  

free()：  原型：void free (void* list);

  C语言中，free可以释放calloc, malloc, realloc动态分配的空间，注意：释放的不是自己定义的指针，而是定义的指针指向的空间。自己定义的普通指针能不能可以通过free
释放，这个要看情况。如果定义的指针指向动态分配的地址空间，则可以使用free释放指针指向的这段空间；否则，就不能使用free释放指针指向的空间。