链表

1.单链表

1.1单链表的插入与查找

头文件 head.h

#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 255
typedef struct{//数据域的元素
int id;
char *name;
}ElementType;
typedef struct{
ElementType datas[MAX_SIZE];
int length;
}SeqList;
//定义链表的结点，包含数据域和指针域
typedef struct Node{
    ElementType data;//数据域
    struct Node *next;//指针域，指向下一个结点
}Node;
/*
头结点
注意：我们在定义链表时，习惯性的会定义头结点，以便对链表结点的插入和删除操作比较统一
头结点也可以称为首元结点，最后一个结点叫做尾元结点
*/
typedef struct LinkList{
Node * next;//头指针(如果链表有头结点，next就指向头结点，没有就指向第一个结点)
int length;//链表长度，初始值为0
}LinkList;
//初始化链表
void InitLinkList(LinkList *linkList,ElementType *dataArray,int length);
//在指定的位置pos处插入元素element
void InsertLinkList(LinkList *linkList,int pos,ElementType element);
//打印链表数据
void printLinkList(LinkList *linkList);
//链表是否为空
int IsLinkListEmpty(LinkList *linkList);
//得到这个元素，返回pos位置的元素
ElementType GetLinkListElement(LinkList *linkList,int pos);
//删除并返回指定位置的元素
ElementType DeleteLinkListElement(LinkList *linkList,int pos);
//清空链表
void ClearLinkList(LinkList * linkList);

基本操作.cpp LinkList.cpp

#include <iostream>
using namespace std;
#include "head.h"


//初始化链表
int i;
void InitLinkList(LinkList *linkList,ElementType *dataArray,int length){
    for(i=0;i<length;i++){
    InsertLinkList(linkList,i+1,dataArray[i]);
    }
}
//在指定的位置pos处插入元素element
void InsertLinkList(LinkList *linkList,int pos,ElementType element){
    //1.创建空结点并为数据域赋值
    Node *node=(Node *)malloc(sizeof(Node));
    node->data=element;
    node->next =NULL;

    //2.找到要插入位置的结点
    if(pos==1){//如果插入的是第一个元素，就很简单
        linkList->next=node;
        linkList->length++;//增加的是头结点的数量
        return ;
    }
    //通过循环找到要插入的结点位置
    Node * currNode=linkList->next;
    for(i=1;currNode &&i<pos-1;i++){
    currNode=currNode->next;//传到要插入位置的前一个结点
    }
    //3.将结点插入并对接前面的结点
if(currNode){
        node->next=currNode->next;
        currNode->next=node;
        linkList->length++;
    }
}

//打印链表
void printLinkList(LinkList *linkList){
Node *node=linkList->next;
if(!node){
printf("链表为空\n");
linkList->length=0;
return ;
}
for(i=0;i<linkList->length;i++){//下面输出循环没用到i,
printf("%d\t%s\n",node->data.id,node->data.name);
node=node->next;
}
}

//链表是否为空
int IsLinkListEmpty(LinkList *linkList){//长度为0，链表为空
return linkList->length==0 ? true : false;
}

//得到这个元素,返回pos位置的元素
ElementType GetLinkListElement(LinkList *linkList,int pos){
    Node *node=linkList->next;
    for(i=1;node && i<pos;i++){//节点不能为空
    node=node->next;
    }
    return node->data;
}

//删除并返回指定位置的元素
ElementType DeleteLinkListElement(LinkList *linkList,int pos){
    ElementType element; //被删除的元素
    element.id=-999;  //赋一个不可能的值，用来判断是否删除成功
    Node *node=NULL;

    if(pos==1){
    node=linkList->next;
    if(node!=NULL){
    element=node->data;
    linkList->next=node->next;
    free(node);
    linkList->length--;
    }
    return element;
}

    //找到要删除结点和它的前缀结点
    //要删除结点->next赋值给前缀结点->next
    //释放要删除的结点内存
    Node *preNode;
    node=linkList->next;
    for(i=1;node && i<pos;i++){
    preNode=node;
    node=node->next;
    if(node){
    element=node->data;
    preNode->next=node->next;
    free(node);
    linkList->length--;
    }
    }
    return element;
}

//删除单链表，释放内存空间
void ClearLinkList(LinkList * linkList){
    Node * node=linkList->next;
    Node *nextNode;
    while(node){
    nextNode=node->next;//先记录当前结点的下一个结点，以便释放当前结点的内存
    free(node);
    node=nextNode;
    }
    linkList->next=NULL;
}

main.cpp

#include <iostream>
using namespace std;
#include<string.h>
#include<stdio.h>
#include<stdlib.h>

#include "head.h"


void TestLinkList();


ElementType dataArray[]={
    {1,"啊"},
    {2,"按"},
    {3,"阿"},
    {4,"唉"}
};

void TestLinkList(){
    LinkList linkList;
    linkList.length=0;
    InitLinkList(&linkList,dataArray,sizeof(dataArray)/sizeof(dataArray[0]));


    //在不同位置插入元素

    ElementType element;
    element.id=123;
    element.name=(char *)malloc(10);
    strcpy_s(element.name,10,"测试1");
    InsertLinkList(&linkList,2,element);
    printf("插入后：\n");
    printLinkList(&linkList);

    //删除
    printf("删除第1个元素后：\n");
    DeleteLinkListElement(&linkList,1);
    printLinkList(&linkList);

    printf("清空链表:\n");
    ClearLinkList(&linkList);
    printLinkList(&linkList);
}

int main(){
    TestLinkList();
    system("pause");
    return 0;
}

1.1.2问题

1. for(i=0;i<length;i++){

   InsertLinkList(linkList,i+1,dataArray[i]);
   }
   在C语言中，必须先定义后使用

1.2顺序表

1.2.1顺序表基本操作

DataElement.h

//用来定义数据元素

#define MAX_SIZE 255

//定义数据元素
typedef struct {
int id;
char * name;
}ElementType;

//定义顺序表结构
typedef struct{
    ElementType datas[MAX_SIZE];//顺序表中的数据元素集合
    int length;//当前顺序表中的元素个数
}SeqList;

SequenceList.h

//定义顺序表
#include <stdio.h>
#include <stdlib.h>
#include "DataElement.h"

//初始化顺序表
void InitList(SeqList * seqList,ElementType *elementArray,int length);

//按照下标插入元素
void InsertElement(SeqList *seqList,int index,ElementType element);

//打印
void PrintList(SeqList* seqLiat);

//删除顺序表中指定下标的元素，返回删除的元素，如果删除失败返回Null
ElementType * DeleteElement(SeqList* seqList,int index);

//返回指定下标的元素
ElementType *GetElement(SeqList *seqList,int index);

//返回顺序表的长度
int GetLength(SeqList * seqList);

//返回顺序表是否为空
int IsEmpty(SeqList *seqList);

//清空顺序表
void ClearList(SeqList *seqList);

SequenceList.cpp

#include "SequenceList.h"

int i;
int j;
//初始化顺序表
void InitList(SeqList * seqList,ElementType *elemArray,int length){
    if(length>MAX_SIZE){
    printf("超出了最大容量%d\n",length);
    }
    seqList->length=0;
    for(i=0;i<length;i++){
    //每次循环都在下标为i的位置插入一个元素
        InsertElement(seqList,i,elemArray[i]);
    }
}

//按照下标插入元素
void InsertElement(SeqList *seqList,int index,ElementType element){
    //验证插入后的空间是否超过MAX_SIZE
    //index的值是否合法[0,MAX_SIZE-1]
    //插入的index应该在length之内
    //从第length-1个下标开始，前面一个元素赋值给后面一个元素
    if(seqList->length+1 >=MAX_SIZE){
    printf("数组已满，插入元素失败%d\n",seqList->length);
    return ;
    }
    if(index<0||index >MAX_SIZE-1){
    printf("超出范围la\n");
    return ;
    }
    if(index > seqList->length){
        printf("超出范围啦%d%d\n",index,seqList->length);
        return;
    }
    //从最后一个到要插入的序号复制并后退一个
    for(j=seqList->length-1;j>=index;j--){
        seqList->datas[j+1]=seqList->datas[j];
    }
    seqList->datas[index]=element;
    //顺序表的总长度加1
    seqList->length++;
}

//删除顺序表中指定下标的元素，返回删除的元素，如果删除失败返回Null
ElementType * DeleteElement(SeqList* seqList,int index){


    if(index<0 || index>MAX_SIZE){
    printf("下标越界，无法删除指定下标的元素\n");
    return NULL;
    }
    //1.找到要删除的元素，并保存以便返回(保存的是已删除元素的副本)
    ElementType * delElement=(ElementType *)malloc(sizeof(ElementType));
    //单独定义并调用查找函数，返回要删除元素的指针
    *delElement=*GetElement(seqList,index);

    //2.从指定位置删除，后面一个元素赋值给前面一个元素
    for(i=index;i<seqList->length;i++){
    seqList->datas[i]=seqList->datas[i+1];
    }
    seqList->length--;
    //3.顺序表的总长度-1

    return delElement;//建议使用完毕后进行free，否则会造成内存泄露
}

//返回指定下标的元素
ElementType *GetElement(SeqList *seqList,int index){
    if(index<0 || index>MAX_SIZE){
    printf("下标越界，无法找到指定下标的元素\n");
    return NULL;
    }
    ElementType *element;//要查找的元素
    element=&seqList->datas[index];
    return element;
}


//返回顺序表的长度
int GetLength(SeqList * seqList){
    if(seqList==NULL)
        return 0;
return seqList->length;
}

//返回顺序表是否为空
int IsEmpty(SeqList *seqList){
return GetLength(seqList)==0 ? 0 :seqList->length;
}

//清空顺序表
void ClearList(SeqList *seqList){
    if(seqList==NULL){
    return;
    }
    sewList->length=0;
}


//打印
void PrintList(SeqList * seqList){
    for(i=0;i<seqList->length;i++){
    printf("%d\t%s\t%d\n",seqList->datas[i].id,seqList->datas[i].name,i);
    }
}

main.cpp

#include <stdio.h>
#include <stdlib.h>
#include "SequenceList.h"



ElementType dataArray[]={
    {1,"萧炎"},
    {2,"唐三"},
    {3,"林动"},
    {4,"叶笑"}
};


void TestSequenceList();


void TestSequenceList(){
    SeqList seqList;

    InitList(&seqList,dataArray,sizeof(dataArray)/sizeof(dataArray[0]));
    PrintList(&seqList);
    ElementType *delElement;

    delElement=DeleteElement(&seqList,2);
    printf("删除后:\n");
    PrintList(&seqList);
    printf("被删除的元素：\n");
    printf("%d\t%s\n",delElement->id,delElement->name);
    free(delElement);//一定要记得释放资源
}
int main(){
    TestSequenceList();
    system("pause");
return 0;
}

1.2.2问题

1. ElementType DeleteElement(SeqList seqList,int index){};
   用地址传值：局部变量只能在函数内变化和传递，不能传到外边去。
   2. 变量要定义不同变量，当进程运行时，一个变量名是互通的
   如下图，InsertElement函数里面的for循环的i与InitList函数里面的i相等，所有会跟着改变，要定义不同的变量。 ```cpp int i; //初始化顺序表 void InitList(SeqList seqList,ElementType elemArray,int length){ if(length>MAX_SIZE){ printf(“超出了最大容量%d\n”,length); } seqList->length=0; for(i=0;i<length;i++){ //每次循环都在下标为i的位置插入一个元素 InsertElement(seqList,i,elemArray[i]); } }

//按照下标插入元素 void InsertElement(SeqList *seqList,int index,ElementType element){ //验证插入后的空间是否超过MAX_SIZE //index的值是否合法[0,MAX_SIZE-1] //插入的index应该在length之内 //从第length-1个下标开始，前面一个元素赋值给后面一个元素 if(seqList->length+1 >=MAX_SIZE){ printf(“数组已满，插入元素失败%d\n”,seqList->length); return ; } if(index<0||index >MAX_SIZE-1){ printf(“超出范围la\n”); return ; } if(index > seqList->length){ printf(“超出范围啦%d%d\n”,index,seqList->length); return; } //从最后一个到要插入的序号复制并后退一个 for(i=seqList->length-1;i>=index;i—){ seqList->datas[i+1]=seqList->datas[i]; } seqList->datas[index]=element; //顺序表的总长度加1 seqList->length++; }

<a name="NNtYj"></a>
## 1.3循环链表



<a name="iIBgg"></a>
## 1.4双向链表
DataElement.h
```cpp
//用来定义数据元素

#define MAX_SIZE 255

//定义数据元素
typedef struct {
int id;
char * name;
}ElementType;

//定义顺序表结构
typedef struct{
    ElementType datas[MAX_SIZE];//顺序表中的数据元素集合
    int length;//当前顺序表中的元素个数
}SeqList;

doublyLinkList.h

//在单链表的基础上增加了前缀结点，一定程度上提升了查找元素的速度
//在查找元素时，可以反向查找前缀结点

#include <stdlib.h>
#include <stdio.h>
#include "DataElement.h"

//双向链表的结点，包含一个数据域，两个指针域
typedef struct DoublyNode{
    ElementType data;
    struct DoublyNode *prev;//前缀结点
    struct DoublyNode *next;//后继结点
}DoublyNode;

//双向链表
typedef struct DoublyLinkList{
    int length;
    DoublyNode *next;//头指针
}DoublyLinkList;

//向双向链表中的指定位置插入元素
void InsertDoublyLinkList(DoublyLinkList *dlList,int pos,ElementType element);

//打印链表
void PrintDoublyLinkList(DoublyLinkList *dlList);

doublyLinkList.cpp

#include "doublyLinkList.h"

//向双向链表中的指定位置插入元素
void InsertDoublyLinkList(DoublyLinkList *dlList,int pos,ElementType element){
    //创建空结点
    DoublyNode *node=(DoublyNode *)malloc(sizeof(DoublyNode));
    node->data=element;
    node->prev=NULL;
    node->next=NULL;

    //在第一个位置插入结点
    if(pos==1){
    node->next=dlList->next;
    dlList->next=node;
    node->next->prev=node;
    dlList->length++;
    return;
    }

    DoublyNode * currNode=dlList->next;
    for(int i=1;currNode && i<pos-1;i++){//当前结点不为0
    currNode=currNode->next;
    }
    if(currNode){
    node->prev=currNode;
    if(currNode->next){//如果前缀结点非空(空就表示没有后继结点了)
        //将插入位置处的前缀结点指向新结点
        currNode->next->prev=node;
    }
    node->next=currNode->next;
    currNode->next=node;
    dlList->length++;
    }
}

//打印链表
void PrintDoublyLinkList(DoublyLinkList *dlList){
    DoublyNode *node=dlList->next;
    if(!node ||dlList->length==0){
    printf("链表为空，没有内容可以打印\n");
    dlList->length=0;
    return;
    }
    for(int j=0;j<dlList->length;j++){
    printf("%d\t%s\n",node->data.id,node->data.name);
    node=node->next;
    }


}

链接2021.11.15 21:35