链表

#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);

#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被释放，则头结点的下一个指针也被释放掉了。
    node=nextNode;
    }
    linkList->next=NULL;
}

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

#include "head.h"


void TestLinkList();


ElementType dataArray[]={
    {1,"12.1"},
    {2,"12.2"},
    {3,"12.3"},
    {4,"12.4"}
};

void TestLinkList(){
    LinkList linkList;
    linkList.length=0;
    InitLinkList(&linkList,dataArray,sizeof(dataArray)/sizeof(dataArray[0]));
    printf(" 初始化后：\n");
    printLinkList(&linkList);

    //在不同位置插入元素

    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;
}