jtahstu的博客

root@jtahstu.com   Github   英文博客  

最新碎语:以后没事写写小的知识点吧

您的位置:jtahstu的博客 >算法> 数据结构与算法从了解到懵逼 - 顺序表和链表

数据结构与算法从了解到懵逼 - 顺序表和链表

顺序表


#include <stdio.h>
typedef struct {
    char key[15];  //结点的关键字
    char name[20];
    int age;
} DATA;    //定义结点类型,可定义为简单类型,也可定义为结构

#include <string.h>
#define MAXSIZE 100  //定义线性表的最大长度

typedef struct {  //定义顺序表结构
    DATA ListData[MAXSIZE+1]; //保存顺序表的数组
    int ListLen;              //顺序表已存结点 的数量
} SeqListType;

void SeqListInit(SeqListType *SL); //初始化顺序表
int SeqListLength(SeqListType *SL);  //返回顺序表的元素数量
int SeqListAdd(SeqListType *SL,DATA data); //向顺序表中添加元素
int SeqListInsert(SeqListType *SL,int n,DATA data); //向顺序表中插入元素
int SeqListDelete(SeqListType *SL,int n);  //删除顺序表中的据元素
DATA *SeqListFindByNum(SeqListType *SL,int n);  //根据序号返回元素
int SeqListFindByCont(SeqListType *SL,char *key); //按关键字查找
int SeqListAll(SeqListType *SL);//遍历顺序表中的内容

void SeqListInit(SeqListType *SL) { //初始化顺序表
    SL->ListLen=0;     //初始化时,设置顺序表长度为0
}
int SeqListLength(SeqListType *SL) { //返回顺序表的元素数量
    return (SL->ListLen);
}
int SeqListAdd(SeqListType *SL,DATA data) { //增加元素到顺序表尾部
    if(SL->ListLen>=MAXSIZE) { //顺序表已满
        printf("顺序表已满,不能再添加结点了!\n");
        return 0;
    }
    SL->ListData[++SL->ListLen]=data;
    return 1;
}
int SeqListInsert(SeqListType *SL,int n,DATA data) {
    int i;
    if(SL->ListLen>=MAXSIZE) { //顺序表结点数量已超过最大数量
        printf("顺序表已满,不能插入结点!\n");
        return 0;             //返回0表示插入不成功
    }
    if(n<1 || n>SL->ListLen-1) { //插入结点序号不正确
        printf("插入元素序号错误,不能插入元素!\n");
        return 0;              //返回0,表示插入不成功
    }
    for(i=SL->ListLen; i>=n; i--) //将顺序表中的数据向后移动
        SL->ListData[i+1]=SL->ListData[i];
    SL->ListData[n]=data;        //插入结点
    SL->ListLen++;               //顺序表结点数量增加1
    return 1;                   //返回成功插入
}
int SeqListDelete(SeqListType *SL,int n) { //删除顺序表中的数据元素
    int i;
    if(n<1 || n>SL->ListLen+1) { //删除元素序号不正确
        printf("删除结点序号错误,不能删除结点!\n");
        return 0;              //返回0,表示删除不成功
    }
    for(i=n; i<SL->ListLen; i++) //将顺序表中的数据向前移动
        SL->ListData[i]=SL->ListData[i+1];
    SL->ListLen--;               //顺序表元素数量减1
    return 1;                   //返回成功删除
}
DATA *SeqListFindByNum(SeqListType *SL,int n) { //根据序号返回数据元素
    if(n<1 || n>SL->ListLen+1) { //元素序号不正确
        printf("结点序号错误,不能返回结点!\n");
        return NULL;              //返回0,表示不成功
    }
    return &(SL->ListData[n]);
}
int SeqListFindByCont(SeqListType *SL,char *key) { //按关键字查询结点
    int i;
    for(i=1; i<=SL->ListLen; i++)
        if(strcmp(SL->ListData[i].key,key)==0)  //如果找到所需结点
            return i;        //返回结点序号
    return 0;  //遍历后仍没有找到,则返回0
}

int SeqListAll(SeqListType *SL) { //遍历顺序表中的结点
    int i;
    for(i=1; i<=SL->ListLen; i++)
        printf("(%s,%s,%d)\n",SL->ListData[i].key,SL->ListData[i].name,SL->ListData[i].age);
}
int main() {
    int i;
    SeqListType SL;         //定义顺序表变量
    DATA data,*data1;       //定义结点保存数据类型变量和指针变量
    char key[15];           //保存关键字

    SeqListInit(&SL);       //初始化顺序表

    do {                    //循环添加结点数据
        printf("输入添加的结点(学号 姓名 年龄):");
        fflush(stdin);              //清空输入缓冲区
        scanf("%s%s%d",&data.key,&data.name,&data.age);
        if(data.age) {                                  //若年龄不为0
            if(!SeqListAdd(&SL,data))                   //若添加结点失败
                break;                                  //退出死循环
        } else   //若年龄为0
            break;          //退出死循环
    } while(1);
    printf("\n顺序表中的结点顺序为:\n");
    SeqListAll(&SL);                     //显示所有结点数据

    fflush(stdin);                       //清空输入缓冲区
    printf("\n要取出结点的序号:");
    scanf("%d",&i);                 //输入结占点序号
    data1=SeqListFindByNum(&SL,i);  //按序号查找结点
    if(data1)                       //若返回的结点指针不为NULL
        printf("第%d个结点为:(%s,%s,%d)\n",i,data1->key,data1->name,data1->age);

    fflush(stdin);                                                             //清空输入缓冲区
    printf("\n要查找结点的关键字:");
    scanf("%s",key);  //输入关键字
    i=SeqListFindByCont(&SL,key);      //按关键字查找 ,返回结点序号
    data1=SeqListFindByNum(&SL,i);     //按序号查询,返回结点指针
    if(data1)                          //若结点指针不为NULL
        printf("第%d个结点为:(%s,%s,%d)\n",i,data1->key,data1->name,data1->age);
    getch();
    return 0;
}


链表


#include <stdio.h>
typedef struct {
    char key[15];	//关键字
    char name[20];
    int age;
} DATA; 	//数据结点类型
#include <stdlib.h>
typedef struct Node {
    DATA data;
    struct Node *next;
} ChainListType;
ChainListType *ChainListAddEnd(ChainListType *head,DATA data);  //添加结点到链表末尾
ChainListType *ChainListAddFirst(ChainListType *head,DATA data);  //添加结点到链表首部
ChainListType *ChainListFind(ChainListType *head,char *key); //按关键字在链表中查找内容
ChainListType *ChainListInsert(ChainListType *head,char *findkey,DATA data);  //插入结点到链表指定位置
int ChainListDelete(ChainListType *head,char *key);//删除指定关键字的结点
int ChainListLength(ChainListType *head);//获取链表结点数量

//#include "2-5 ChainList.c"
#include <string.h>
ChainListType *ChainListAddEnd(ChainListType *head,DATA data) { //添加结点到链表结尾
    ChainListType *node,*h;
    if(!(node=(ChainListType *)malloc(sizeof(ChainListType)))) {
        printf("为保存结点数据申请内存失败!\n");
        return NULL;  //分配内存失败
    }
    node->data=data; //保存数据
    node->next=NULL;  //设置结点指针为空,即为表尾
    if(head==NULL) { //是头指针
        head=node;
        return head;
    }
    h=head;
    while(h->next!=NULL) //查找链表的末尾
        h=h->next ;
    h->next=node;
    return head;
}
ChainListType *ChainListAddFirst(ChainListType *head,DATA data) {
    ChainListType *node,*h;
    if(!(node=(ChainListType *)malloc(sizeof(ChainListType)))) {
        printf("为保存结点数据申请内存失败!\n");
        return NULL;  //分配内存失败
    }
    node->data=data; //保存数据
    node->next=head;  //指向头指针所指结点
    head=node;        //头指针指向新增结点
    return head;
}
ChainListType *ChainListInsert(ChainListType *head,char *findkey,DATA data) { //插入结点到链表指定位置
    ChainListType *node,*node1;
    if(!(node=(ChainListType *)malloc(sizeof(ChainListType)))) { //分配保存结点的内容
        printf("为保存结点数据申请内存失败!\n");
        return 0;  //分配内存失败
    }
    node->data=data;  //保存结点中的数据
    node1=ChainListFind(head,findkey);
    if(node1) { //若找到要插入的结点
        node->next=node1->next;  //新插入结点指向关键结点的下一结点
        node1->next=node;    //设置关键结点指向新插入结点
    } else {
        free(node);//释放内存
        printf("未找到插入位置!\n");
    }
    return head;//返回头指针
}
ChainListType *ChainListFind(ChainListType *head,char *key) { //按关键字在链表中查找内容
    ChainListType *h;
    h=head;       //保存链表头指针
    while(h) {    //若结点有效,则进行查找
        if(strcmp(h->data.key,key)==0) //若结点关键字与传入关键字相同
            return h;  //返回该结点指针
        h=h->next; //处理下一结点
    }
    return NULL; //返回空指针
}
int ChainListDelete(ChainListType *head,char *key) {
    ChainListType *node,*h; //node保存删除结点的前一结点
    node=h=head;
    while(h) {
        if(strcmp(h->data.key,key)==0) { //找到关键字,执行删除操作
            node->next=h->next;  //使前一结点指向当前结点的下一结点
            free(h);  //释放内存
            return 1;
        } else {
            node=h;  //指向当前结点
            h=h->next; //指向下一结点
        }
    }
    return 0;//未删除
}
int ChainListLength(ChainListType *head) { //获取链表结点数量
    ChainListType *h;
    int i=0;
    h=head;
    while(h) {    //遍历整个链表
        i++; //累加结点数量
        h=h->next;//处理下一结点
    }
    return i;//返回结点数量
}

void ChainListAll(ChainListType *head) { //遍历链表
    ChainListType *h;
    DATA data;
    h=head;
    printf("链表所有数据如下:\n");
    while(h) { //循环处理链表每个结点
        data=h->data;//获取结点数据
        printf("(%s,%s,%d)\n",data.key,data.name,data.age);
        h=h->next;//处理下一结点
    }
    return;
}
int main() {
    ChainListType *node, *head=NULL;
    DATA data;
    char key[15],findkey[15];

    printf("输入链表中的数据,包括关键字、姓名、年龄,关键字输入0,则退出:\n");
    do {
        fflush(stdin);  //清空输入缓冲区
        scanf("%s",data.key);
        if(strcmp(data.key,"0")==0) break; //若输入0,则退出
        scanf("%s%d",data.name,&data.age);
        head=ChainListAddEnd(head,data);//在链表尾部添加结点数据
    } while(1);

    printf("该链表共有%d个结点。\n",ChainListLength(head)); //返回结点数量
    ChainListAll(head); //显示所有结点

    printf("\n插入结点,输入插入位置的关键字:") ;
    scanf("%s",&findkey);//输入插入位置关键字
    printf("输入插入结点的数据(关键字 姓名 年龄):");
    scanf("%s%s%d",data.key,data.name,&data.age);//输入插入结点数据
    head=ChainListInsert(head,findkey,data);//调用插入函数

    ChainListAll(head); //显示所有结点

    printf("\n在链表中查找,输入查找关键字:");
    fflush(stdin);//清空输入缓冲区
    scanf("%s",key);//输入查找关键字
    node=ChainListFind(head,key);//调用查找函数,返回结点指针
    if(node) { //若返回结点指针有效
        data=node->data;//获取结点的数据
        printf("关键字%s对应的结点数据为(%s,%s,%d)\n" ,key,data.key,data.name,data.age);
    } else//若结点指针无效
        printf("在链表中未找到关键字为%s的结点!\n",key);

    printf("\n在链表中删除结点,输入要删除的关键字:");
    fflush(stdin);//清空输入缓冲区
    scanf("%s",key);//输入删除结点关键字
    ChainListDelete(head,key); //调用删除结点函数
    ChainListAll(head); //显示所有结点
    getch();
    return 0;
}
    代码为书上的源代码,此文章只作学习和回顾作用,闲来可以看看,仅此。


---

本文章采用 知识共享署名2.5中国大陆许可协议 进行许可,欢迎转载,演绎或用于商业目的。

---

二维码加载中...

扫一扫移动端访问O(∩_∩)O

发表评论

92 + 33 =
路人甲 表情
看不清楚?点图切换 Ctrl+Enter快速提交
正在加载中……