数据结构（一）线性表(1）

写在前面

第一次写博客想说说自己的目的噢 本人是大一新生，IT蒟蒻，可能暂时写不出有质量的文章，所以只是想把自己的学习过程记录下来（说难听点就是写给自己看的博客）。 不过以后多多少少我的文章也会派上用场的吧（希望） 希望我能够坚持写下去，至少在本科四年里。因为之前写日记都是写着写着就忘了有日记这回事（其实就是太懒） 好吧那不喜勿喷（虽然也没几个人会看） 内容如若出错还望各位大佬多包涵且指正

----------------------------------------------------我是分割线------------------------------------------------------

最近在自学数据结构，线性表差不多算是搞懂了 线性表的概念就不多讲了，毕竟概念性的东西看看书都能理解 主要讲讲各类表的C代码实现（没办法目前只会C）

一、线性表顺序存储结构

//首先要预处理一些东西 //头文件不多说 #include<stdio.h> //定义线性表最大长度 #define MAXSIZE 100 //定义一些标志性常量 #define ERROR 0 #define OK 1 #define TRUE 1 #define FALSE 0 //重命名 typedef int Elemtype; typedef int Status; //然后定义线性表结构并实现一些功能（操作线性表的功能） typedef struct SqList { Elemtype data[MAXSIZE]; //存储数据 int length; //线性表当前长度 }SqList; //与打印结合 Status visit(Elemtype c) { printf("%d ",c); return OK; } //初始化顺序线性表 Status InitList(SqList *L) { L->length=0; return OK; } //判断线性表是否为空表 Status ListEmpty(SqList L) { if(L.length==0) return TRUE; else return FALSE; } //清空线性表 Status ClearList(SqList *L) { L->length=0; //直接把长度改为0即可 数据不用管 因为存入数据时可覆盖 return OK; } //获得线性表长度 int ListLength(SqList L) { return L.length; } //获得线性表中第i个位置的元素 Status GetElem(SqList L,int i,ElemType *e) { if(L.length==0 || i<1 || i>L.length) return ERROR; *e=L.data[i-1]; return OK; } //判断线性表中是否存在元素e，若存在则返回该元素位置，若不存在则返回0 int LocateElem(SqList L,ElemType e) { int i; if (L.length==0) return 0; for(i=0;i<L.length;i++) { if (L.data[i]==e) break; } if(i>=L.length) return 0; return i+1; } //在线性表第i个位置插入元素e Status ListInsert(SqList *L,int i,ElemType e) { int k; if (L->length==MAXSIZE) // 顺序线性表已经满 return ERROR; if (i<1 || i>L->length+1)// 当i比第一位置小或者比最后一位置后一位置还要大时 return ERROR; if (i<=L->length) // 若插入数据位置不在表尾 { for(k=L->length-1;k>=i-1;k--) // 将要插入位置之后的数据元素向后移动一位 L->data[k+1]=L->data[k]; } L->data[i-1]=e; // 将新元素插入 L->length++; return OK; } //删除线性表中第i个位置的元素，并用e返回该元素值 Status ListDelete(SqList *L,int i,ElemType *e) { int k; if (L->length==0) // 线性表为空 return ERROR; if (i<1 || i>L->length) // 删除位置不正确 return ERROR; *e=L->data[i-1]; if (i<L->length) // 如果删除不是最后位置 { for(k=i;k<L->length;k++)// 将删除位置后继元素前移 L->data[k-1]=L->data[k]; } L->length--; return OK; } //打印线性表每个元素 Status ListTraverse(SqList L) { int i; for(i=0;i<L.length;i++) visit(L.data[i]); printf("\n"); return OK; } //合并两个链表 void unionL(SqList *La,SqList Lb) { int La_len,Lb_len,i; ElemType e; La_len=ListLength(*La); Lb_len=ListLength(Lb); for (i=1;i<=Lb_len;i++) { GetElem(Lb,i,&e); if (!LocateElem(*La,e)) ListInsert(La,++La_len,e); } }

二、单链表

//头文件不多说 #include<stdio.h> #include<stdlib.h> //定义一些标志性常量 #define ERROR 0 #define OK 1 #define TRUE 1 #define FALSE 0 //重命名 typedef int Elemtype; typedef int Status; //然后定义线性表结构并实现一些功能（操作线性表的功能） typedef struct Node { ElemType data; //数据域 struct Node *next;//指针域--指向下个结点 }Node,*LinkList; //与打印结合 Status visit(ElemType c) { printf("%d ",c); return OK; } //初始化链表（带头结点的链表） Status InitList(LinkList *L) { *L=(LinkList)malloc(sizeof(Node)); // 产生头结点,并使L指向此头结点 if(!(*L)) // 存储分配失败 return ERROR; (*L)->next=NULL; // 指针域置为空 return OK; } //判断链表是否为空 Status ListEmpty(LinkList L) { if(L->next) return FALSE; else return TRUE; } //清空链表 Status ClearList(LinkList *L) { LinkList p,q; p=(*L)->next; // p指向第一个结点 while(p) // 没到表尾 { q=p->next; free(p); p=q; } (*L)->next=NULL; // 头结点指针域置为空 return OK; } //计算链表长度 int ListLength(LinkList L) { int i=0; LinkList p=L->next; // p指向第一个结点 while(p) { i++; p=p->next; } return i; } //寻找链表中i位置的元素，用e获取其值 Status GetElem(LinkList L,int i,ElemType *e) { int j; LinkList p; // 声明一结点p p = L->next; // 让p指向链表L的第一个结点 j = 1; // j为计数器 while (p && j<i) // p不为空或者计数器j还没有等于i时，循环继续 { p = p->next; // 让p指向下一个结点 ++j; } if ( !p || j>i ) return ERROR; // 第i个元素不存在 *e = p->data; // 取第i个元素的数据 return OK; } //寻找元素e，若找到则返回其位序，若不存在则返回0 int LocateElem(LinkList L,ElemType e) { int i=0; LinkList p=L->next; while(p) { i++; if(p->data==e) // 找到这样的数据元素 return i; p=p->next; } return 0; } //在第i个位置插入元素e Status ListInsert(LinkList *L,int i,ElemType e) { int j; LinkList p,s; p = *L; j = 1; while (p && j < i) // 寻找第i个结点 { p = p->next; ++j; } if (!p || j > i) return ERROR; // 第i个元素不存在 s = (LinkList)malloc(sizeof(Node)); // 生成新结点(C语言标准函数) s->data = e; s->next = p->next; // 将p的后继结点赋值给s的后继 p->next = s; // 将s赋值给p的后继 return OK; } //删除第i个位置的元素，并用e返回其值 Status ListDelete(LinkList *L,int i,ElemType *e) { int j; LinkList p,q; p = *L; j = 1; while (p->next && j < i) // 遍历寻找第i个元素 { p = p->next; ++j; } if (!(p->next) || j > i) return ERROR; // 第i个元素不存在 q = p->next; p->next = q->next; // 将q的后继赋值给p的后继 *e = q->data; // 将q结点中的数据给e free(q); // 让系统回收此结点，释放内存 return OK; } //打印链表中元素 Status ListDis(LinkList L) { LinkList p=L->next; while(p) { visit(p->data); p=p->next; } printf("\n"); return OK; } //头插法 void CreateListHead(LinkList *L, int n) { LinkList p; int i; srand(time(0)); // 初始化随机数种子 *L = (LinkList)malloc(sizeof(Node)); (*L)->next = NULL; // 先建立一个带头结点的单链表 for (i=0; i<n; i++) { p = (LinkList)malloc(sizeof(Node)); // 生成新结点 p->data = rand()%100+1; // 随机生成100以内的数字 p->next = (*L)->next; (*L)->next = p; // 插入到表头 } } //尾插法 void CreateListTail(LinkList *L, int n) { LinkList p,r; int i; srand(time(0)); // 初始化随机数种子 *L = (LinkList)malloc(sizeof(Node)); // L为整个线性表 r=*L; // r为指向尾部的结点 for (i=0; i<n; i++) { p = (Node *)malloc(sizeof(Node)); // 生成新结点 */ p->data = rand()%100+1; // 随机生成100以内的数字 r->next=p; // 将表尾终端结点的指针指向新结点 r = p; // 将当前的新结点定义为表尾终端结点 } r->next = NULL; // 表示当前链表结束 }

-------------------------------------------------我也是分割线------------------------------------------------------

写在最后 下一篇的内容可能是基于主成分分析的人脸识别（因为最近有个project，数据结构被迫停学emmmmm） 小萌新将要开启第一次看论文之旅（希望我成功归来）