学习笔记1

链表

线性表链式存储结构（链表）：

1、链表结点由数据域和指针域构成。

2、头结点：在开始结点之前的结点。其值域不包含任何信息。

3、首元素结点：第一个元素所在的结点。

4、头指针：一直指向链表中第一个结点的位置（如果表中不含头节点则头指针指向开始结点）。

5、单链表
带头结点的单链表：头指针head指向头结点。头指针head始终不等于NULL，head->next等于NULL的时候该链表为空。
不带头结点的单链表：头节点head指向开始结点，当head等于NULL时该链表为空。

6、头结点和头指针的区别：头指针是一个指针，头指针指向链表的第一个结点（如果链表有头结点，头指针指向头结点；否则，
头指针指向开始结点）；头结点是一个实际存在的点，它包含有数据域和指针域。头指针指向目标地址声明而没有分配存储空间，
而头结点分配了一个结点的实际物理内存。

单链表的结构定义：

typedef struct Node // 结点类型定义
 { //ElemType 具体数据的类型据实际设定, 整型或者字符型等等
	ElemType data； 
	struct Node * next；
 }Node, *LinkList；

初始化链表

InitList(LinkList *L) 
{
	*L = (LinkList)malloc(sizeof(Node));
	 (*L)->next=NULL; 
}

单链表头插法代码示例:

void CreateFromTail(LinkList L)
{ 
	Node *r, *s; int flag=1;//标记初值为1,当输入“$”时,标记flag为0,建表结束输入 
	r=L; while(flag) 
	{ 
	c=getchar();//接收一字符
		if(c!=’$’) //如果字符不是’$’,则执行头插
		{
				s=(Node *)malloc(sizeof(Node)); 
			s->datac;
			s->next=L->next;
			L->next=s;
		}
		else
                {                
			flag=0; r->next=NULL;
                }
	}
}

单链表尾插法代码示例:

void CreateFromTail(LinkList L)
{ 
    Node *r, *s; int flag=1;//标志--初值为1,当输入“$”时,flag为0,建表结束
     r=L; 
    while(flag)
    {
     c=getchar();//接收一字符 
        if(c!=’$’) //如果字符不是’$’,则执行尾插 
           {
                s=(Node *)malloc(sizeof(Node)); 
                s->data=c; 
                r->next=s; 
                r=s;
            }
        else 
            {
                flag=0; r->next=NULL;
            }
    }
}

在表中任意位置插入一个节点：

void InsList(LinkList L,int i,ElemType n)
{ 
/*在带头结点的单链表L中第i个结点之前插入一个值为n的新结点。 */
Node *pre,*s;
int k; 
if(i<1) return Error;
pre=L; 
k=0;
    while(pre!=NULL&&k<i-1)
    { 
        pre=pre->next;
        k=k+1; 
    } 
    if(!pre) 
    {
        printf(“插入位置不合理！”)； 
        return Error; 
    } 
    s=(Node*)malloc(sizeof(Node)); //为n申请一个新的结点
    s->data=e; /*将待插入结点的值n赋给s的数据域*/ 
    s->next=pre->next;
    pre->next=s; 
    return OK;
}

删除单链表中的一个节点：

void DelList(LinkList L,int i,ElemType *e) 
{ 
Node *pre,*r;
int k; 
pre=L; 
k =0; 
    while(pre->next!=NULL&&k<i-1) 
    { 
        pre=pre->next;
        k=k+1; 
    } 
    if( !(pre->next) ) 
    { 
        printf(“删除结点的位置i不合理！”);
        return ERROR; 
    } 
    r=pre->next;
    pre->next=pre->next->next /*删除结点r*/ 
    e = r->data; 
    free(r); 
    return OK; 
}

以上是本次对单链表的基本知识以及增删改查操作的部分学习记录