数据结构考前复习（4）

&x：取x的地址   

*x取地址x的存储内容

深入理解C语言指针

参考：深入理解C语言指针_ZackSock的博客-CSDN博客_深入理解c指针

C语言中->含义

参考：含义，比如说 p=p->next_skyang在路上-CSDN博客_c语言->next">C语言中->含义，比如说 p=p->next_skyang在路上-CSDN博客_c语言->next

p->a  :p所指向的结构体中包含的数据a

struct Data
{
int a,b,c;
}; 
struct Data * p;                 
struct Data A = {1,2,3};         / *  声明结构体变量A，A即结构体名   */
int x;                               
p = &A ;                           
x = p->a;        

对于 p = p->next;其中的next应该是自定义的一个与p同类型的结构体指针，定义格式为：

struct Data 
{
   int a;
   struct Data * next;
};
…………
main()
{
   struct Data * p;
  ……
   p = p->next;
}

1.结点和单链表的C语言描述

//------线性表的单链表存储结构------
typedef struct LNnode
{
	Elemtype data;//数据域
	struct LNnode *next; //指针域 
} LNode,*linkList;
//L为单链表的头指针
linkList L; 

2.函数GetElem在单链表中的实现

Status GetElem_L(linkList L,int i,ElemType &e)
//L为带头结点的单链表的头指针
//当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
{
	p=L->next;
	j=1;
	//初始化，p指向第一个结点，j为计数器 
	while(p&&jnext;
		++j; 
	}
	if(!p||j>i)
		return ERROR;//第i个元素不存在 
	e=p->data;//取第i个元素
	return OK; 
} 

3.函数ListInsert在单链表中的实现

已知p为指向结点a的指针，要在结点a、b之间插入一个数据p

假设s为指向结点x的指针，则指针修改用语句描述为：

s->next=p->next; p->next=s;

Status ListInsert_L(linkList &L,int i,ElemType e)
 //在带头结点的单链线性表L中的第i个位置插入元素e 
 {
	p=L;
	j=0;
	while(p&&jnext;
		 ++j;	
 	} //寻找第i-1个结点
	if(!p||j>i-1)
	 	return ERROR;//i小于1或者大于表长+1
	s=(linkList)malloc(sizeof(LNode));//生成新结点
	s->data=e;
	s->next=p->next; //插入L中 
	p->next=s;
	return OK;
 }

4.函数ListDelete在单链表中的实现

要删除元素b时，假设p为指向结点a的指针，则修改指针的语句为：

p->next=p->next->next; 

 status ListDelete_L(linkList &L,int i,ElemType &e)
 //在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
 {
 	p=L;
 	j=0;
 	while(p->next&&jnext;
 		++j;
	}
	if(p->next||j>i-1)
		return ERROR;//删除位置不合理 
	q=p->next;
	p=q->next;//删除并释放结点
	e=q->data;
	free(q);
	return OK; 
 } 

注：

s=(linkList)malloc(sizeof(LNode))的作用是由系统生成一个LNode型的结点，同时将该点的起始位置赋给指针变量s；

执行free(q)的作用是回收一个LNode型的结点，，回收后的空间可以备作再次再次生成结点时用。