[数据结构与算法]11.21周记

（什么是链表。

链表是一种常见的基础数据结构，结构体指针在这里得到了充分的利用。链表可以动态的进行存储分配，也就是说，链表是一个功能极为强大的数组，他可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。链表都有一个头指针，一般以head来表示，存放的是一个地址。

head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”

(1).建立简单的静态链表。

#include <stdio.h>
struct Student
{
	int num;
	float score;
	struct Student *next;
	
};
int main()
{
	struct Student a,b,c,*head,*p;
	a.num=10101;a.score=89.5;
	b.num=10103;b.score=90;
    c.num=10107;c.score=89;
	
	head=&a;
	a.next=&b;
	b.next=&c;
	c.next=NULL;
	p=head;
	do
	{
		printf("%ld %5.1f\n",p->num,p->score);
		p=p->next;
	}while(p!=NULL);
	return 0;
}

为了建立链表，使head指向a结点，a.next指向b结点，b.next指向c结点。构成一个链表。

再让c.next=null。

静态链表的所有结点都是定义的，不是临时开辟的，也不能用完后释放。

（2）建立动态链表。

#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(struct student)


struct student{
long num;
float score;
struct student *next;
};

int n;
struct student *creat(void)
{
struct student *head,*p1,*p2;
n=0;
p1=p2=(struct student *)malloc(LEN);         //用malloc函数开辟第一个节点。
   
scanf("%d,%f",&p1->num,&p1->score);         //向 p1 指针指向的地址添加数据

head=NULL;                                  // 先让头指针为空
while(p1->num!=0)  //约定学号不为0
{
n=n+1;
if(n==1)
head=p1;      //将 p1 指针 指向的地址赋给 head     
else
p2->next=p1;   
p2=p1;       //将 p1 所指向的地址赋给 p2  


p1=(struct student *)malloc(LEN);   // p1 再重新指向一个新开辟的地址       
scanf("%d,%f",&p1->num,&p1->score);  //输入其他学生的数据
}
p2->next=NULL;  //最后赋予NULL；
    return(head);
}


int main(){
struct student *pt;
pt=creat();

printf("%d %5.1f ",pt->num,pt->score);

   printf("\n");
}

分析

这个算法的思路是让p1指向新开辟的结点，p2指向链表中最后一个结点，把p1所指向的结点连接在p2所指向的结点后面。

（3）输出链表。

#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(struct student)
struct student{
long num;
float score;
struct student *next;
};

int n;
void print(struct Student *head) 
{
	struct Student *p;
	p=head;
	if(head!=NULL)
	do{
		printf("%d %5.1f\n",p->num,p->score);
		p=p->next;
	}while(p!=NULL);
	
}

知道head的值，然后设一个指针变量p，先指向第一个结点，输出p所指的结点，然后使p后移一个结点，再输出，直到链表的尾结点。

（4）关于链表的基本操作

求单链表表长

int length(linklist L)
{
int l=0;
while(L->next!=0)
   {l++;
    L=L-next;
    }
  return l;
}

修改链表结点值

void change(LinkList *list,int n) {//n为第n个节点
	LinkList *t = list;
	int i = 0;
	while (i < n && t != NULL) {
		t = t->next;
		i++;
	}
	if (t != NULL) {
		puts("输入要修改的值");
		scanf("%d", &t->score);
	}
	else {
		puts("节点不存在");
	}
}

删除链表结点

void delet(LinkList *list, int n) {
	LinkList *q = list, *p;
	int i = 0;
	while (i < n && t != NULL) {
		p = q;
		q = q->next;
		i++;
	}
	if (t != NULL) {
		p->next = q->next;
		free(t);
	}
	else {
		printf("节点不存在");
	}
}