2.3-线性表的链式表示

单链表的实现和基本操作

// 单链表的操作

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct LNode{// 定义单链表节点类型
    ElemType data;        // 数据域
    struct LNode *next;    //指针域
}LNode, *LinkList;

// 头插法
LinkList List_HeadInsert(LinkList &L){
    LNode *s;
    int x;

    L = (LinkList)malloc(sizeof(LNode));    // 创建头节点
    L->next = NULL;                            //初始化为空链表

    scanf("%d", &x);
    while( x != 999 ){
        s = (LNode*)malloc(sizeof(LNode));    // 创建新结点(分配空间,把地址赋值给 s)
        s->data = x;
        s->next = L->next;        // L 为头指针
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

// 尾插法
LinkList List_TailInsert(LinkList &L){
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s;
    LNode *r = L;    // 表尾指针

    scanf("%d", &x);
    while( x != 999 ){
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;        // 插入结点赋值
        r->next = s;        // 新结点插入表中
        r = s;                // 地址赋给尾结点,r 指向新的表尾结点,作为下一次插入的临时区
        scanf("%d", &x);
    }
    r->next = NULL;            // 尾结点指针置空
    return L;
}

// 按照序号查找结点值(带头结点)
LNode *GetElem(LinkList L, int i){
    int j = 1;                // 计数,初始值为1
    LNode *p = L->next;        // 头结点赋值给 p
    if(i == 0){
        return L;
    }
    if(i < 1){
        return NULL;
    }
    while (p && j < i){        // 从第1个开始查找
        p = p->next;
        j++;
    }
    return p;                // 返回第 i 个结点的指针,i 大于表长, p = NULL, 直接返回p即可
}

// 删除第 i 个结点
bool List_Delete(LinkList L, int i){
    LinkList p = GetElem(L, i - 1); // 查找删除位置的前驱结点
    if(p == NULL){
        return false;
    }
    LinkList q;
    q = p->next;            // q 指向被删除结点
    p->next = q->next;        // *q从链中断开 相当于 p->next = p->next->next;,但不能这么写,因为要释放qDLinkList
    free(q);                // 释放结点储存空间
    return true;
}

// 位置插入
bool ListFrontInsert(LinkList L, int i, ElemType e){
    // 创建新结点
    LinkList s = (LNode*)malloc(sizeof(LNode));
    s->data = e; 

    LinkList p = GetElem(L, i-1); // 插入位置前驱结点
    if(NULL == p){
        return false;
    }
    s->next = p->next; // 新结点指向当前位置对应结点
    p->next = s;    // 插入位置前驱结点指向当前插入结点
    return true;
}

// 打印链表
void List_Print(LinkList L){
    L = L->next;
    while (L != NULL){
        printf("%3d", L->data);
        L = L->next;
    }
    printf("\n");
}


int main(void){
    LinkList L;
    LinkList search;

    List_TailInsert(L);
    List_Print(L);

    search = GetElem(L, 2);
    if(search != NULL){
        printf("%d\n", search->data);
    }

    printf("位置插入:\n");
    ListFrontInsert(L, 2, 99);
    List_Print(L);
    printf("位置删除:\n");
    List_Delete(L, 4);
    List_Print(L);
    
    return 0;
}

双链表的实现和基本操作

// 双链表
// 结论:画示意图后参照写步骤
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

typedef int ElemType;

typedef struct DNode{    // 定义双链表节点类型
    ElemType data;        // 数据域
    struct DNode *prior, *next;    // 前驱和后继指针
}DNode, *DLinklist;

// 头插法
DLinklist DList_head_insert(DLinklist &DL){
    DNode *s;
    int x;

    DL = (DLinklist)malloc(sizeof(DNode));// 创建空链表
    DL->next = NULL;
    DL->prior = NULL;
    scanf("%d", &x);

    while(x != 999){
        s = (DNode*)malloc(sizeof(DNode));// 创建新节点
        s->data = x; // 数据域赋值

        s->next = DL->next; // *s 插入到 *DL 之后         ---1
        if(DL->next != NULL){
            DL->next->prior = s;// 第一个节点指向插入的 s     ---2
        }
        s->prior = DL;                                //    ---3

        DL->next = s;                                //    ---4 , 1、2必须在4之前
        scanf("%d", &x);
    }
    return DL;
}

// 尾插法
DLinklist DList_tail_insert(DLinklist &DL){
    int x;
    DL = (DLinklist)malloc(sizeof(DNode));
    DNode *s, *r = DL;

    DL->prior = NULL;
    scanf("%d",&x);
    while(x != 999){
        s = (DNode*)malloc(sizeof(DNode));
        s->data = x;
        r->next = s;
        s->prior = r;
        r = s;
        scanf("%d",&x);
    }
    r->next = NULL;
    return DL;
}

// 取元素
DNode *GetElem(DLinklist DL, int i){
    int j = 1;
    DNode *p = DL->next;

    if(i == 0){
        return DL;
    }
    if(i < 1){
        return NULL;
    }

    while(p && j < i){
        p = p->next;
        j++;
    }
    return p;
}

// 元素头部插入 (p 之后插入 s)
bool DListFrontInsert(DLinklist DL, int i, ElemType e){
    DLinklist p = GetElem(DL, i-1);
    if(p == NULL){
        return false;
    }
    DLinklist s = (DNode*)malloc(sizeof(DNode));
    s->data = e;

    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
    return true;
}

// 元素删除
bool DListDelete(DLinklist DL, int i){
    DLinklist p = GetElem(DL, i-1);
    if(p == NULL){
        return false;
    }
    DLinklist q;
    q = p->next;
    if(q == NULL){
        return false;
    }
    p->next = q->next;
    if(q->next != NULL){
        q->next->prior = p;
    }
    free(q);                // 需要释放内存
    return true;
}

// 打印
void PrintDList(DLinklist DL){
    DL = DL->next;
    while(DL != NULL){
        printf("%3d\n", DL->data);
        DL = DL->next;
    }
    printf("\n");
}

int main(void){
    DLinklist DL;
    DLinklist search;

    // DList_head_insert(DL);
    DList_tail_insert(DL);
    printf("尾插法结果:\n");
    PrintDList(DL);

    search = GetElem(DL, 2);
    if(search != NULL){
        printf("序号查找:");
        printf("%d\n\n", search->data);
    }

    DListFrontInsert(DL, 3, 666);
    printf("3位置插入:\n");
    PrintDList(DL);


    DListDelete(DL, 3);
    printf("3位置删除:\n");
    PrintDList(DL);

    return 0;
}

课后代码题目

本文链接:https://ariser.cn/index.php/archives/106/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!