软讯网络 > 编程语言 > C/C++ > C数据结构_带头接点的单链表的实现
【标 题】：C数据结构_带头接点的单链表的实现
【关键字】：
【来 源】：http://www.cublog.cn/u/17227/showart.php?id=232260
C数据结构_带头接点的单链表的实现
/************************************
单链表实现
链表带有头节点
在VC6 中调试成功
vincent
2007-01-08
*************************************/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
/*申明结构，节点*/
typedef struct LNode{
ElemType data;
LNode *next;
}LNode,*LinkList;
/*定义一个函数指针在LocateElem作为函数参数使用*/
typedef Status (*cmp)(LNode* i, LNode* x);
typedef void (*vis)( LNode* N);
/*创建LinkList,注意结构作为函数参数时的特别之处,头节点中的data放置链表长度(元素个数)*/
LinkList InitList();
LinkList InitList(int i);
/*销毁LinkList,注意要销毁整个链表*/
Status DestroyList(LinkList L);
/*将元素插入链表指定位置*/
Status InsertList(LinkList L, int i, ElemType e);
/*删除链表中的指定元素*/
Status DeletList(LinkList L, int i);
/*获取链表中指定位置的元素:注意链表中的元素就是它的节点*/
LNode* GetElem(LinkList L, int i);
/*获取链表长度,因为头节点data记录即其长度，但是这样的结构在非int类型的data中有问题*/
int ListLength(LinkList L);
/*定位元素位置*/
int LocateElem(LinkList L,LNode* N, cmp f);
/*前一个元素*/
LNode* PriorElem(LinkList L);
/*后一个元素*/
LNode* NextElem(LinkList L);
/*遍历链表*/
void ListTraverse(LinkList L, vis v);
/*比较2个节点是否相同*/
Status Compare(LNode* i, LNode* x);
/*visit 节点*/
void Visit(LNode* N);
/*主程序*/
void main(){
printf("单链表实现，头节点存放链表长度\n");
printf("首先生成一个含5个节点的单链表\n");
int i ;
LinkList L = InitList(5);
/*注意这里函数指针的用法*/
vis v = Visit;
ListTraverse(L,v);
DestroyList(L);
}
/*创建LinkList,注意结构作为函数参数时的特别之处,头节点中的data放置链表长度(元素个数)*/
LinkList InitList( ){
LinkList L = (LinkList) malloc(sizeof(LNode));
if (!L) exit(OVERFLOW);
L->data = 0;
L->next = NULL;
return L;
}
LinkList InitList(int i){
int t ;
LinkList L = (LinkList)malloc(sizeof(LNode));
if (!L) exit(OVERFLOW);
L->data = 0;
L->next = NULL;
for(t = 0; t < i ; t++){
LinkList P = (LinkList)malloc(sizeof(LNode));
if(!P) exit(OVERFLOW);
scanf("%d",&P->data);
P->next = L->next;
L->next = P;
++L->data;
}
return L;
}
/*销毁LinkList,注意要销毁整个链表*/
Status DestroyList(LinkList L){
int length = 0;
LinkList t = L;
LinkList p = L;
if (!L) exit(ERROR);
if (!L->next){
free(L);
L = NULL;
return OK;
}
t = L->next;
while(t->next){
p = t->next;
free(t);
t = p;
}
t = NULL;
p = NULL;
free(L);
L = NULL;
return OK;
}
/*将元素插入链表指定位置之后*/
Status InsertList(LinkList L, int i, ElemType e){
int j;
if(!L) exit(ERROR);
if(i > L->data) exit(ERROR);
LinkList p = (LinkList) malloc(sizeof(LNode));
LinkList t = L;
if(!p) exit(OVERFLOW);
p->data = e;
for(j = 0; j < i; j++){
t = t->next;
}
p->next = t->next;
t->next = p;
++L->data;
return OK;
}
/*删除链表中的指定位置的元素*/
Status DeletList(LinkList L, int i){
int j ;
LinkList &t = L;
if(!L) exit(ERROR);
if(i > L->data || i < 1) exit(ERROR);
for(j = 0; j < i; j++){
t = t->next;
}
LinkList &p = t;
p = p->next;
t->next = p->next;
free(p);
--L->data;
return OK;
}
/*获取链表中指定位置的元素:注意链表中的元素就是它的节点*/
LNode* GetElem(LinkList L, int i){
int j ;
LNode* N;
LinkList &t = L;
if(!L) exit(ERROR);
if( i< 1 || i > L->data) exit(ERROR);
for(j = 0; j <= i; j++){
t = t->next;
}
N = (LNode*) t;
return N;
}
/*获取链表长度,因为头节点data记录即其长度，但是这样的结构在非int类型的data中有问题*/
int ListLength(LinkList L){
if(!L) exit(ERROR);
return L->data;
}
/*定位元素位置*/
int LocateElem(LinkList L,LNode* N, cmp f){
LNode* t;
if(!L)exit(ERROR);
LinkList &p = L->next;
int j;
for(j = 1; j <= L->data; j++){
t = (LNode*)p;
if(f(N,t)) return j;
p = p->next;
}
return 0;
}
/*比较2个节点是否相同*/
Status Compare(LNode* i, LNode* x){
if(!i || !x)exit(ERROR);
if(i->data == x->data)return(TRUE);
return FALSE;
}
/*前一个元素*/
LNode* PriorElem(LinkList L){
/*在单链表中实现查找前一个元素的算法基本不可能，在此不实现*/
return 0;
}
/*后一个元素*/
LNode* NextElem(LinkList L){
if(!L || !L->next)exit(ERROR);
return (LNode*)L->next;
}
/*遍历链表*/
void ListTraverse(LinkList L, vis v){
if(!L)exit(ERROR);
/*L 为单链表的头节点*/
L = L->next;
while(L){
(LNode*)L;
v(L);
L = L->next;
}
}
/*visit 节点*/
void Visit(LNode* N){
if(!N)exit(ERROR);
printf("%d\n",N->data);
}
【相关文章】
没有相关文章
|