【数据结构】之 线性表详解(3)

定义：

单链表的存储结构如下：

typedef struct Node{
    char ch;
    int len;    //表长度 
    struct Node *next;
}Node,*linkList;

?

创建

单链表的创建有两种：头插法和尾插法

代码在这里：

//尾插法建立表 
linkList createFromTail(linkList L){
    Node *s,*r;    //r指针始终指向链表尾部 
    char ch;
    int flag = 1;
    r = L;
    printf("尾插法建立表,请输入数据并以'#'结束输入：\n");
    while(flag){
        printf("输入数据: ");
        scanf("%c",&ch);
        getchar();
        if(ch == '#'){
            //若输入 # 则退出 
            flag = 0;
            r->next = NULL;
        }else{
            s = (linkList)malloc(sizeof(Node));
            s->ch = ch;
            r->next = s;
            r = s;
            (L->len)++; 
            flag = 1;
        }
    } 
    print(L);
    return L;
} 

??

基本操作

其基本操作和顺序表一样：查找，插入，删除。

查找

这里也只讲按值查找

【算法思想】：从单链表的头指针指向的头结点出发，顺链逐个将结点值和给定值作比较。

【算法描述】

//按内容查找
linkList getAsContent(linkList L){
    Node *p;
    char ch;
    int i = 1; 
    
    p = L->next;
    printf("\n请输入查找内容：");
    scanf("%c",&ch);
    getchar();
    
    //遍历完表且未找到数据退出循环， 找到数据时退出函数 
    while(p != NULL){
        if(p->ch == ch){
            printf("按内容查找成功，第 %d 个位置的数据为 %c\n",p->ch);
            return p;
        }
        p = p->next;
        i++;
    }
    
    //未找到数据
    if(p == NULL){
        printf("按内容查找失败！未在表中找到数据！\n");
    }
} 

?

插入

【算法思想】：首先要找到插入位置i的前一个结点，并用指针pre指向它，然后申请新结点s，通过修改pre和s的指针域将新结点插入链表。

【算法描述】

//插入
linkList insertList(linkList L){
    Node *pre,*s;
    int k,i;
    char ch;
    pre = L;
    k = 0;
    printf("\n请输入你要插入的位置和内容(格式: address content)：");
    scanf("%d %c",&i,&ch);
    getchar();
    
    //插入位置不可能为负 
    if(i <= 0){
        printf("插入失败！插入位置不合法！插入位置不能为负\n");
        return NULL;
    }
    
    ////遍历完表且未找到插入位置(此时i大于表的长度) 或 找到插入位置时退出函数 退出循环
    while(pre != NULL && k < i - 1){
        pre = pre->next;
        k++;
    }
    
    if(pre == NULL){
        
        // 未找到插入位置(此时i大于表的长度)
        printf("插入失败！插入位置不合法！插入位置超出表的长度\n");
        return NULL;
    }else{
        
        //找到插入位置并插入数据 
        s = (linkList)malloc(sizeof(Node));
        s->ch = ch;
        s->next = pre->next;
        pre->next = s;
        L->len++;
        printf("插入成功！");
        print(L);
        return L;
    }
} 

?

删除

【算法思想】：通过计数方式找到删除位置的前一个结点并用pre指针指向它，然后删除结点并释放空间。

（编辑：ASP站长网）