#include <stdlib.h>
#include <math.h>
#define ElemType int
#define Status int
#define TRUE 1
#define OK 1
#define FALSE 0
#define ERROR -1
/*线性表的单链表存储结构*/
typedef struct LNode
{
ElemType data
struct LNode *next
}LNode, *LinkList
/*带有头结点的单链表的基本操作(12个)*/
void InitList(LinkList *L)
{ /* 操作结果:构造一个空的线性表L */
*L=(LinkList)malloc(sizeof(struct LNode))/* 产生头结点,并使L指向此头结点 */
if(!*L) /* 存储分配失败 */
exit(OVERFLOW)
(*L)->next=NULL/* 指针域为空 */
}
void DestroyList(LinkList *L)
{ /* 初始条件:线性表L已存在。操作结果:销毁线性表L */
LinkList q
while(*L)
{
q=(*L)->next
free(*L)
*L=q
}
}
void ClearList(LinkList L) /* 不改变L */
{ /* 初始条件:线性表L已存在。操作结果:将L重置为空表 */
LinkList p,q
p=L->next/* p指向第一个结点 */
while(p) /* 没到表尾 */
{
q=p->next
free(p)
p=q
}
L->next=NULL/* 头结点指针域为空 */
}
Status ListEmpty(LinkList L)
{ /* 初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE */
if(L->next) /* 非空 */
return FALSE
else
return TRUE
}
int ListLength(LinkList L)
{ /* 初始条件:线性表L已存在。操作结果:返回L中数据元素个数 */
int i=0
LinkList p=L->next/* p指向第一个结点 */
while(p) /* 没到表尾 */
{
i++
p=p->next
}
return i
}
Status GetElem(LinkList L,int i,ElemType *e) /* 算法2.8 */
{ /* L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */
int j=1/* j为计数器 */
LinkList p=L->next/* p指向第一个结点 */
while(p&&j <i) /* 顺指针向后查找,直到p指向第i个元素或p为空 */
{
p=p->next
j++
}
if(!p||j>i) /* 第i个元素不存在 */
return ERROR
*e=p->data/* 取第i个元素 */
return OK
}
int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ /* 初始条件: 线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0) */
/* 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。 */
/* 若这样的数据元素不存在,则返回值为0 */
int i=0
LinkList p=L->next
while(p)
{
i++
if(compare(p->data,e)) /* 找到这样的数据元素 */
return i
p=p->next
}
return 0
}
Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
{ /* 初始条件: 线性表L已存在 */
/* 操作结果: 若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱, */
/* 返回OK;否则操作失败,pre_e无定义,返回INFEASIBLE */
LinkList q,p=L->next/* p指向第一个结点 */
while(p->next) /* p所指结点有后继 */
{
q=p->next/* q为p的后继 */
if(q->data==cur_e)
{
*pre_e=p->data
return OK
}
p=q/* p向后移 */
}
return ERROR
}
Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e)
{ /* 初始条件:线性表L已存在 */
/* 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继, */
/* 返回OK否则操作失败,next_e无定义,返回INFEASIBLE */
LinkList p=L->next/* p指向第一个结点 */
while(p->next) /* p所指结点有后继 */
{
if(p->data==cur_e)
{
*next_e=p->next->data
return OK
}
p=p->next
}
return ERROR
}
Status ListInsert(LinkList L,int i,ElemType e) /* 算法2.9。不改变L */
{ /* 在带头结点的单链线性表L中第i个位置之前插入元素e */
int j=0
LinkList p=L,s
while(p&&j <i-1) /* 寻找第i-1个结点 */
{
p=p->next
j++
}
if(!p||j>i-1) /* i小于1或者大于表长 */
return ERROR
s=(LinkList)malloc(sizeof(struct LNode))/* 生成新结点 */
s->data=e/* 插入L中 */
s->next=p->next
p->next=s
return OK
}
Status ListDelete(LinkList L,int i,ElemType *e) /* 算法2.10。不改变L */
{ /* 在带头结点的单链线性表L中,删除第i个元素,并由e返回其值 */
int j=0
LinkList p=L,q
while(p->next&&j<i-1) /* 寻找第i个结点,并令p指向其前岖 */
{
p=p->next
j++
}
if(!p->next||j>i-1) /* 删除位置不合理 */
return ERROR
q=p->next/* 删除并释放结点 */
p->next=q->next
*e=q->data
free(q)
return OK
}
void ListTraverse(LinkList L,void(*vi)(ElemType))
/* vi的形参类型为ElemType,与bo2-1.c中相应函数的形参类型ElemType&不同 */
{ /* 初始条件:线性表L已存在。操作结果:依次对L的每个数据元素调用函数vi() */
LinkList p=L->next
while(p)
{
vi(p->data)
p=p->next
}
printf("\n")
}
void ListPrint(LinkList L)
{
LinkList p=L->next
while(p)
{
printf("%d ", p->data)
p = p->next
}
printf("\n")
}
void ListSort(LinkList L)
{
LinkList first/*为原链表剩下用于直接插入排序的节点头指针*/
LinkList t/*临时指针变量:插入节点*/
LinkList p/*临时指针变量*/
LinkList q/*临时指针变量*/
first = L->next/*原链表剩下用于直接插入排序的节点链表*/
L->next = NULL/*只含有一个节点的链表的有序链表。*/
while (first != NULL) /*遍历剩下无序的链表*/
{
/*插入排序*/
for (t = first, q = L((q!=NULL) &&(q->data <t->data))p=q, q=q->next)/*无序节点在有序链表中找插入的位置*/
/*退出for循环,就是找到了插入的位置*/
first = first->next/*无序链表中的节点离开,以便它插入到有序链表中。*/
if (q == L) L = t/*插在第一个节点之前*/
else p->next = t/*p是q的前驱*/
t->next = q/*完成插入动作*/
}
}
void main()
{
LinkList L
int e
InitList(&L)
ListInsert(L, 1, 2)
ListInsert(L, 1, 3)
ListInsert(L, 1, 67)
ListInsert(L, 1, 6)
ListInsert(L, 1, 5)
ListDelete(L, 2, &e)
ListSort(L)
ListPrint(L)
}
链条没听说过,链表但是知道。其实是一种数据结构,常用的结构还有栈(汇编必学),队列,和树(这种结构对于提高效率相当有用。)
如果是初学就不要想这些了,老实地把基础打好,可以地话,认真越好你的数学,,真正的计算机大牛还是强在算法,结构,思想,设计上。而且越学你会发现自己知道的越少。C语言是一种极端,然而lisp是另一种极端,我现在才开始接触函数式编程这东东,才知道思想无止境啊。
因为堆栈是链式栈,是否满栈取决于堆存储的大小。堆空间耗尽时,可以狭义地理解为栈满。那么在编程时,可以用一个变量保存栈元素的个数。栈是否满,取决于申请动态内存时的返回值,如
Stack *p = (Stack *)malloc(sizeof(Stack));,若(p == NULL),则栈满。