数据结构知识点(2)

struct Node * next; }Node,*Linklist;

void CreatFromHead(LinkList L) {

Node *s,*r; r=L; char c; int flag=1; 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; } } }

3、单链表查找

1）按序号查找

算法描述：设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从头结点(L->next)开始顺着链域扫描，用指针p指向当前扫描到的结点，初值指向头结点,用j做计数器，累计当前扫描过的结点数(初值为0)，当j=i时，指针p所指的结点就是要找的第i个结点。 算法：

typedef struct Node {

ElemType data; struct Node * next; }Node,*Linklist;

Node * Get(LinkList L,int i) {

int j=0; Node *p; p=L:

if(i<=0) return NULL; /*找的序号太小*/ while((p->next!=NULL)&&(jnext; j++; }

if(p->next==NULL) return NULL; /*找不到i*/ else return i; /*找到了i*/ }

2）按值查找

算法描述：按值查找是指在单链表中查找是否有节点值等于e的结点，若有的话，则返回首次找到的其值等于e的结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。 算法：

typedef struct Node {

ElemType data; struct Node * next; }Node,*Linklist;

Node *Locate(LinkList L,ElemType key) {

Node *p; p=L->next;

while(p!=NULL) { if(p->data==key) return p; /*找到了key*/ p=p->next; }

return NULL; /*没有找到了key*/

}

4、单链表插入操作

问题要求：在线性表的第i(1?i?n?1)个位置之前插入一个新元素e。 算法思想：

?查找：在单链表中找到第i-1个结点并有指针pre指示。 ?申请：申请新节点s，将其数据域的值置为e；

?插入挂链：通过修改指针域将新节点s挂入单链表L。 算法：

typedef struct Node {

ElemType data; struct Node * next; }Node,*Linklist;

void Inslist(ElemType e,int i,LinkList L) {

Node *pre,*s; int k;

if(i<=0) return ERROR; pre=L;k=0;

while(pre!=NULL&&knext; k++; } if(k==i) { s=(Node *)malloc(sizeof(Node)); s->data=e; s->next=pre->next; pre->next=s; return OK; } else { printf(\插入位置不合理\); return ERROR; } }

5、单链表删除

问题要求：将线性表的第i(1?i?n?1)个元素e删除 算法思想：

?查找：通过计数方式找到第i-1个结点并由指针pre指示； ?删除第i个结点并释放结点空间。

结果：将长度为n的线性表(a1,?,ai?1,ai,?,an)变成长度为n-1 的线性表(a1,?,ai?1,ai?1,?,an) 算法：

typedef struct Node {

ElemType data; struct Node * next; }Node,*Linklist;

void DelList(LinkList L,int i,ElemType *e) {

Node *pre,*s; int k;

if(i<=0) return ERROR; pre=L;k=0;

/*按序号查找第i个位置*/ while(pre->next!=NULL&&knext; k++; }

if(pre->next==NULL) { printf(\删除位置错误\); return ERROR; }

s=pre->next; /*使得删除得第i个位置的指针为s*/ pre->next=s->next; *e=s->data;

free(s); /*释放被删除的结点所占的内存空间*/ return OK; }

算法应用举例

1、求单链表的长度 算法描述：

可以采用“数”结点的方法来求出单链表的长度，用指针p依次指向各个结点，从第一个元素开始“数”，一直“数”到最后一个结点(p->next=NULL). 算法：

typedef struct Node

{

ElemType data;

struct Node * next; }Node,*LinkList;

int ListLength(LinkList L) {

Node *p; int k=0; p=L:

while(p->next!=NULL) { p=p->next; k++; }

return k; }

2、求两个集合的差

已知：以单链表表示集合，假设集合A用单链表LA表示，集合B用单链表LB表示，设计算法求两个集合的差，即A-B。 算法思想：

由集合运算的规则可知，集合的差A-B中包含所有属于集合A而不属于集合B的元素。具体做法是，对于集合A中的每个元素e，在集合B的链表LB中进行查找，若存在与e相同的元素，则从LA中将其删除。