線性表（單項(xiàng)鏈表）

在C用struct實(shí)現(xiàn)鏈表

• 創(chuàng)建 intList，開(kāi)辟內(nèi)存空間，創(chuàng)建next下一個(gè)節(jié)點(diǎn)為null，如果開(kāi)辟的地址為null返回錯(cuò)誤
• 增加：找到要插入的節(jié)點(diǎn)，創(chuàng)建一個(gè)新的struct，然后插入List里將第一個(gè)list的Next指向插入的struct
• 查找：傳入list，查找需要index，返回elem指針
• 刪除：找到需要?jiǎng)h除的index，把指向上一個(gè)指針指向下一個(gè)，釋放內(nèi)存
• 打?。褐苯友h(huán)鏈表輸出
• 清空，就是一個(gè)一個(gè)的刪除
• 前插法：創(chuàng)建一個(gè)指針結(jié)構(gòu)體，然后一步一步插入

• 記得每次開(kāi)辟空間之后釋放

#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */

typedef int Status;/* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
typedef int ElemType;/* ElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */

//定義結(jié)點(diǎn)
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList;


//2.1 初始化單鏈表線性表
Status InitList(LinkList *L){
    
    //產(chǎn)生頭結(jié)點(diǎn),并使用L指向此頭結(jié)點(diǎn)
    *L = (LinkList)malloc(sizeof(Node));
    //存儲(chǔ)空間分配失敗
    if(*L == NULL) return ERROR;
    //將頭結(jié)點(diǎn)的指針域置空
    (*L)->next = NULL;
    
    return OK;
}


//2.2 單鏈表插入
/*
 初始條件:順序線性表L已存在,1≤i≤ListLength(L);
 操作結(jié)果：在L中第i個(gè)位置之后插入新的數(shù)據(jù)元素e，L的長(zhǎng)度加1;
 */
Status ListInsert(LinkList *L,int i,ElemType e){
 
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    
    //尋找第i-1個(gè)結(jié)點(diǎn)
    while (p && j<i) {
        p = p->next;
        ++j;
    }
    
    //第i個(gè)元素不存在
    if(!p || j>i) return ERROR;
    
    //生成新結(jié)點(diǎn)s
    s = (LinkList)malloc(sizeof(Node));
    //將e賦值給s的數(shù)值域
    s->data = e;
    //將p的后繼結(jié)點(diǎn)賦值給s的后繼
    s->next = p->next;
    //將s賦值給p的后繼
    p->next = s;
    
    return OK;
}


//2.3 單鏈表取值
/*
 初始條件: 順序線性表L已存在,1≤i≤ListLength(L);
 操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值
 */
Status GetElem(LinkList L,int i,ElemType *e){
    
    //j: 計(jì)數(shù).
    int j;
    //聲明結(jié)點(diǎn)p;
    LinkList p;
    
    //將結(jié)點(diǎn)p 指向鏈表L的第一個(gè)結(jié)點(diǎn);
    p = L->next;
    //j計(jì)算=1;
    j = 1;
    
    
    //p不為空,且計(jì)算j不等于i,則循環(huán)繼續(xù)
    while (p && j<i) {
        
        //p指向下一個(gè)結(jié)點(diǎn)
        p = p->next;
        ++j;
    }
    
    //如果p為空或者j>i,則返回error
    if(!p || j > i) return ERROR;
    
    //e = p所指的結(jié)點(diǎn)的data
    *e = p->data;
    return OK;
    
    
}

//2.4 單鏈表刪除元素
/*
 初始條件：順序線性表L已存在，1≤i≤ListLength(L)
 操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，并用e返回其值，L的長(zhǎng)度減1
 */

Status ListDelete(LinkList *L,int i,ElemType *e){
    
    int j;
    LinkList p,q;
    p = (*L)->next;
    j = 1;
    
    //查找第i-1個(gè)結(jié)點(diǎn),p指向該結(jié)點(diǎn)
    while (p->next && j<(i-1)) {
        p = p->next;
        ++j;
    }
    
    //當(dāng)i>n 或者 i<1 時(shí),刪除位置不合理
    if (!(p->next) || (j>i-1)) return  ERROR;
    
    //q指向要?jiǎng)h除的結(jié)點(diǎn)
    q = p->next;
    //將q的后繼賦值給p的后繼
    p->next = q->next;
    //將q結(jié)點(diǎn)中的數(shù)據(jù)給e
    *e = q->data;
    //讓系統(tǒng)回收此結(jié)點(diǎn),釋放內(nèi)存;
    free(q);
    
    return OK;
}

/* 初始條件：順序線性表L已存在 */
/* 操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素輸出 */
Status ListTraverse(LinkList L)
{
    LinkList p=L->next;
    while(p)
    {
        printf("%d\n",p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

/* 初始條件：順序線性表L已存在。操作結(jié)果：將L重置為空表 */
Status ClearList(LinkList *L)
{
    LinkList p,q;
    p=(*L)->next;           /*  p指向第一個(gè)結(jié)點(diǎn) */
    while(p)                /*  沒(méi)到表尾 */
    {
        q=p->next;
        free(p);
        p=q;
    }
    (*L)->next=NULL;        /* 頭結(jié)點(diǎn)指針域?yàn)榭?*/
    return OK;
}

//3.1 單鏈表前插入法
/* 隨機(jī)產(chǎn)生n個(gè)元素值,建立帶表頭結(jié)點(diǎn)的單鏈線性表L(前插法)*/
void CreateListHead(LinkList *L, int n){
    
    LinkList p;
    
    //建立1個(gè)帶頭結(jié)點(diǎn)的單鏈表
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    //循環(huán)前插入隨機(jī)數(shù)據(jù)
    for(int i = 0; i < n;i++)
    {
        //生成新結(jié)點(diǎn)
        p = (LinkList)malloc(sizeof(Node));
       
        //i賦值給新結(jié)點(diǎn)的data
        p->data = i;
        //p->next = 頭結(jié)點(diǎn)的L->next
        p->next = (*L)->next;
        
        //將結(jié)點(diǎn)P插入到頭結(jié)點(diǎn)之后;
        (*L)->next = p;
        
    }
}

//3.2 單鏈表后插入法
/* 隨機(jī)產(chǎn)生n個(gè)元素值,建立帶表頭結(jié)點(diǎn)的單鏈線性表L(后插法)*/
void CreateListTail(LinkList *L, int n){
    
    LinkList p,r;
 
    //建立1個(gè)帶頭結(jié)點(diǎn)的單鏈表
    *L = (LinkList)malloc(sizeof(Node));
    //r指向尾部的結(jié)點(diǎn)
    r = *L;
    
    for (int i=0; i<n; i++) {
        
        //生成新結(jié)點(diǎn)
        p = (Node *)malloc(sizeof(Node));
        p->data = i;
        
        //將表尾終端結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)
        r->next = p;
        //將當(dāng)前的新結(jié)點(diǎn)定義為表尾終端結(jié)點(diǎn)
        r = p;
    }
    
    //將尾指針的next = null
    r->next = NULL;
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    Status iStatus;
    LinkList L1,L;
    struct Node *L2;
    ElemType e;
    
//    L1 =(LinkList) malloc(sizeof(Node));
//    L2 =(LinkList) malloc(sizeof(Node));
//
//    L1->data = 1;
//    L2->data = 2;
//    printf("L1.data=%d,L2.data=%d\n",L1->data,L2->data);
    
    //2.1 單鏈表初始化
    iStatus = InitList(&L);
    printf("L 是否初始化成功?(0:失敗,1:成功) %d\n",iStatus);
    
    //2.2 單鏈表插入數(shù)據(jù)
    for(int j = 1;j<=10;j++)
    {
        iStatus = ListInsert(&L, 1, j);
    }
    printf("L 插入后\n");
    ListTraverse(L);
    
    //2.3 單鏈表獲取元素
    GetElem(L,5,&e);
    printf("第5個(gè)元素的值為：%d\n",e);
    
    //2.4 刪除第5個(gè)元素
    iStatus = ListDelete(&L, 5, &e);
    printf("刪除第5個(gè)元素值為:%d\n",e);
    ListTraverse(L);
    
    //3.1 前插法整理創(chuàng)建鏈表L
    iStatus = ClearList(&L);
    CreateListHead(&L, 20);
    printf("整理創(chuàng)建L的元素(前插法):\n");
    ListTraverse(L);
    
    //3.2 后插法整理創(chuàng)建鏈表L
    iStatus = ClearList(&L);
    CreateListTail(&L, 20);
    printf("整理創(chuàng)建L的元素(后插法):\n");
    ListTraverse(L);
    
}