数据结构-线性表、单链表及双链表
线性表
list.h
//list.h
#ifndef _LIST_H
#define _LIST_H //条件编译语句
#define LIST_INIT_SIZE 10 //线性表初始大小
#define LIST_INCREMENT 10 //递增大小
typedef struct
{
ElemType * elem; //线性表首地址
int length; //线性表当前使用长度
int size; //线性表当前最大长度
}LIST;
LIST *InitList(); //初始化
void FreeList(LIST *l);
int InsertList(LIST* l,int i,ElemType *e);
int DeleteList(LIST *l,int i);
#endif
list.c
//list.c
#include <stdio.h>
#include<stdlib.h>
#include "stu.h"
#include "list.h"
//初始线性表函数
LIST * InitList()
{
LIST* l=(LIST*)malloc(sizeof(LIST));
//在堆中动态定义一个线性表结构指针
if(l==NULL)
{
exit(0);
}
l->elem=(ElemType*)malloc(LIST_INIT_SIZE* sizeof(ElemType));
//在堆中动态开辟数据空间
if(l->elem==NULL)
{
free(l);
exit(0);
}
l->length=0;
l->size=LIST_INIT_SIZE;
return l;
}
void FreeList(LIST *l)
{
free(l->elem); //释放线性表的成员空间
free(l); //释放线性表本身
}
int InsertList(LIST* l,int i,ElemType *e)
{
ElemType *p=NULL,*q=NULL,*newElem=NULL;
if(l==NULL||e==NULL)
return 0;
if(i<1||i>l->length+1)
return 0;
if(l->length>=l->size)
{
newElem=realloc(l->elem,
(l->size+LIST_INCREMENT)*sizeof(ElemType));
if(newElem==NULL)
return 0;
l->elem=newElem;
l->size+=LIST_INCREMENT;
}
q=&l->elem[i-1]; //要插入的位置
for(p=&(l->elem[l->length-1]);p>=q;p--)
*(p+1)=*p; //将p往后移一位
*q=*e; //插入
++l->length;
return 1;
}
int DeleteList(LIST *l,int i)
{
ElemType *p=NULL,*q=NULL;
if(l==NULL)
return 0;
if(i<1||i>l->length)
return 0;
p=&l->elem[i-1];
q=&l->elem[l->length-1];
for(;p<q;p++)
*p=*(p+1);//将后面的元素向前移
--l->length;
return 1;
}
stu.h
//stu.h
#ifndef _STU_H
#define _STU_H
typedef struct //定义一个学生的结构体
{
char sno[5];
char name[21];
char sex[3];
int score;
}ElemType;
#endif
main.c
//main.c
#include <stdio.h>
#include "stu.h"
#include "list.h"
ElemType stu[3]={
{"s010","张三","男",80},
{"s011","张四","男",81},
{"s012","张五","男",82}
};
void main()
{
//定义一个线性性表指针
int i;
LIST* list=NULL;
list=InitList(); //初始化线性表
for(i=0;i<3;i++)
InsertList(list,1,&stu[i]);
DeleteList(list,2);
FreeList(list);
}
单链表
list.h
//list.h
#ifndef _LIST_H
#define _LIST_H
typedef struct _node
{ //结点类型定义
void *data; //结点的数据域
struct _node *next; //结点的指针域
}NODE;
typedef struct
{ //链表类型定义
NODE * head;//头结点
NODE * last;//尾结点
int length;//链表长度
}LIST;
LIST* InitList();
int AddNode(LIST* l,void *data,int size);
NODE* FindNodeByKey(LIST *l,void *key,
int (*compare)(void*,void*)/*函数指针*/);
NODE* FindNode(LIST *l,void *key,
int (*compare)(void*,void*)/*函数指针*/,NODE **pre);
int DeleteListByKey(LIST* l,void* Key,int (*compare)(void*,void*));
#endif
list.c
//list.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
LIST* InitList()
{
LIST* l=(LIST*)malloc(sizeof(LIST)); //创建一个链表
if(l==NULL)
exit(0);
memset(l,0,sizeof(LIST));//将链表清零
return l;
}
int AddNode(LIST* l,void *data,int size) //添加结点
{
//在调试中可以这样看结点的值(struct STU*)l->head->data,(struct STU*)l->last->data
NODE *n=NULL;
if(l==NULL||data==NULL)
return 0;
n=(NODE*)malloc(sizeof(NODE)); //创建一个结点
if(n==NULL)
return 0;
n->data=data;
n->data=malloc(size);
if(n->next=NULL)
{
free(n);
return 0;
}
memcpy(n->data,data,size);//把数据拷到目标结点中去
/*//方法一
if(l->head==NULL)
{
l->head=n;
l->last=n;
l->length=1;
}
else
{
l->last->next=n;//挂在尾结点后面
l->last=n; //改变尾结点的指向
l->length++;
}
*/
//方法二
if(l->head==NULL)
l->head=n;
else
l->last->next=n;
l->last=n;
l->length++;
return 1;
}
NODE* FindNodeByKey(LIST *l,void *key,
int (*compare)(void*,void*)/*函数指针*/)
{ //查找结点
NODE *p=NULL;
if(l==NULL||key==NULL||compare==NULL)
return NULL;
p=l->head;//让p指向第一个结点
while(p)
{
if(compare(p->data,key)==1)//如果返回为1说明找到了
return p;
p=p->next;//否则继续往下找
}
return NULL;//都没找到，返回空
}
NODE* FindNode(LIST *l,void *key,
int (*compare)(void*,void*)/*函数指针*/,NODE **pre)
{ //查找结点,并传入前一个结点的参数
NODE *p=NULL;
if(l==NULL||key==NULL||compare==NULL||pre==NULL)
return NULL;
p=l->head;//让p指向第一个结点
*pre=NULL;
while(p)
{
if(compare(p->data,key)==1)//如果返回为1说明找到了
return p;
*pre=p;//找到的结点的前一个结点
p=p->next;//否则继续往下找
}
return NULL;//都没找到，返回空
}
int DeleteListByKey(LIST* l,void* key,int (*compare)(void*,void*))
{ //删除结点
NODE *p=NULL,*q=NULL;
p=FindNode(l,key,compare,&q/*前一个结点的地址*/);
if(p==NULL)
return 0;
if(q==NULL)//如果前一个结点为空
l->head=p->next;//那么将头指针指向要删除的结点的后一个结点
else
q->next=p->next;
if(p==l->last)
l->last=q;
free(p->data);
free(p);
l->length--;
return 1;
}
main.c
//main.c
#include<string.h>
#include<stdio.h>
#include "list.h"
struct STU
{
char sno[5];
char name[21];
int age;
float score;
}s[3]={
{"s001","lin wu",12,90},
{"s002","xiao ming",13,91},
{"s003","wang wu",11,100}
};
int CompareByName(void *info,void *key)
{
struct STU* stu=(struct STU*)info;
char *name=(char *)key;
return strcmp(stu->name,name)==0?1:0;
}
int CompareBySno(void *info,void *key)
{
struct STU* stu=(struct STU*)info;
char *sno=(char *)key;
return strcmp(stu->sno,sno)==0?1:0;
}
void main()
{
int i;
NODE *res=NULL;//存放找到的结果
char name[]="xiao ming",sno[]="s001";
LIST* list=InitList();
for(i=0;i<3;i++)
AddNode(list,&s[i],sizeof(s[i]));
res=FindNodeByKey(list,name,CompareByName);
if(res==NULL)
printf("NOT Find\n");
else
printf("Find it\n");
if(DeleteListByKey(list,sno,CompareBySno))
printf("delete success\n");
//在调试中可以这样看结点的值(struct STU*)list->head->data,(struct STU*)list->last->data
else
printf("delete fail\n");
}
双链表
list.h
//list.h
#ifndef _LIST_H
#define _LIST_H
typedef struct _node
{
void *data;
struct _node *pior;
struct _node *next;
}NODE;
typedef struct
{
NODE *head;
NODE *last;
int length;
}LIST;
LIST *InitList();
int InsertNode(LIST *l,void *data,int size);
int DeletNode(LIST* l,int n);
void PrintList(LIST *l,int page,int perp,void(*printNode)(void*));
void ClearList(LIST* l);
void DestroyList(LIST **l);
#endif
list.c
//list.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
LIST *InitList()//初始化链表
{
LIST *l=(LIST*)malloc(sizeof(LIST));
if(l==NULL) exit(0);
l->head=(NODE*)malloc(sizeof(NODE));
if(l->head==NULL) exit(0);
memset(l->head,0,sizeof(NODE));
l->last=(NODE*)malloc(sizeof(NODE));
if(l->last==NULL) exit(0);
memset(l->last,0,sizeof(NODE));
//l->head->pior==NULL;
l->head->next=l->last;//将头结点的后续指向尾结点
l->last->pior=l->head;//将尾结点的前驱指向头结点
l->length=0;
return l;
}
int InsertNode(LIST *l,void *data,int size) //插入结点
{
NODE *n=NULL; //定义一个空结点
if(l==NULL||data==NULL||size<=0)//判断传入的参数是否合法
return 0;
n=(NODE*)malloc(sizeof(NODE));//为结点分配空间
if(n==NULL)
return 0;
n->data=malloc(size);//为结点的数据域分配空间
if(n->data==NULL)
{
free(n);
return 0;
}
memcpy(n->data,data,size);//将传入的数据拷贝到结点的数据域当中
n->next=l->last; //它的后继指针指向尾结点
n->pior=l->last->pior; //它的前驱指针指向尾结点的前一个
l->last->pior->next=n; //把尾结点的前一个的后继指针指向它
l->last->pior=n; //把尾结点前驱指针指向它
l->length++; //链表的长度加1
return 1;
}
int DeletNode(LIST* l,int n) //删除结点
{
NODE *p=NULL;
int i=0;
if(l==NULL||n<1||n>l->length)//判断传入的参数是否合法
return 0;
p=l->head->next;//将p指向头结点的下一个
while(i<l->length)//查找第n个结点
{
i++;
if(i==n)
break;
p=p->next;
}
p->pior->next=p->next;//将p的前一个的后继指针指向p的后一个
p->next->pior=p->pior;//将p的后一个的前驱指针指向p的前一个
free(p->data);//释放p结点的数据域
free(p);//释放p结点
l->length--;
return 1;
}
void PrintList(LIST *l,int page,int perP,void(*printNode)(void*))//分布打印链表中的数据
{ //page为页的编号，perP为每页的结点数
int start,end,i;
NODE *p=NULL;
if(l==NULL||printNode==NULL)//判断传入的参数是否有效
return;
start=(page-1)*perP+1;//将在某页面第一条要打印的数据所对映的结点所在链表中的位置
end=page*perP;//将在某页面最后一条要打印的数据所对映的结点所在链表中的位置
p=l->head->next;//将p指向第一个数据结点
i=0;
while(i<l->length && p->next!=NULL)
{
i++;
if(i==start) break;//定位到某页面的第一条要打印的数据
p=p->next;
}
for(;i<=end && p->next!=NULL;i++)//打印某一页面的数据，直到最后一条
{
printNode(p->data);
p=p->next;
}
}
void ClearList(LIST* l)//清空链表
{
NODE *p=NULL;
if(l==NULL)
return;
/*
//方法一
while(l->length)
DeleteNode(l,1);
*/
//方法二
while(l->length)
{
p=l->head->next;//把p指向第一数据结点
l->head->next=p->next;//把头结点的前驱指针指向p的下一个(第一个数据结点)
p->next->pior=l->head;//把p的下一个的前驱指针指向头结点
free(p->data);//释放p指向的结点的数据域
free(p);//释放p结点
l->length--;//链表长度减1
}
}
void DestroyList(LIST **l)//删除链表
{
LIST *p=*l;
//定义一个指向链表l的p指针,并将传入的指向链表的指针变量的值*l,即(*&list)赋给它
//这里指向链表的指针变量的值*l是链表的地址
if(p==NULL) return;
ClearList(p);//清空链表
free(p->head);//释放头结点
free(p->last);//释放尾结点
free(p);//释放指针变量
//p=NULL;
*l=NULL;//将指向链表的指针的值赋成空值，即将指向已经销毁了的链表的指针指向空值
}
main.c
//main.c
#include<stdio.h>
#include "list.h"
double d[5]={10.23,34.23,54.65,122,35.5};
void PrintData(void *data)//打印数据
{
double *d=(double*)data;
printf("d=%lf\n",*d);
}
void main()
{
int i;
LIST *list=InitList();
for(i=0;i<5;i++)
InsertNode(list,&d[i],sizeof(d[i]));
PrintList(list,1,3,PrintData);
DestroyList(&list);//删除链表
//&list 传递指向链表的指针变量地址给DestroyList函数
if(list==NULL)
printf("list is NULL\n");
else
printf("list is not NULL\n");
}