(内容为本人学习记录,如有不足之处,感谢各位指出!)
1.定义单链表结构体typedef struct LNode
{
Elemtype data; //定义数据域
struct LNode *next; //定义指针域
}LNode,*Linklist;
2.初始化——创建一个带头结点的单链表
Linklist InitLinklist(Linklist &L){
L = (LNode*)malloc(sizeof(LNode)); // 分配一个头结点
if (L==NULL){
return NULL;
}
L->next = NULL;
return L;
}
3.头插法建立一个单链表
Linklist List_HeadInsert(Linklist &L){
char c,d; // c待插入的数据,d用于接收输入的空格并过滤
// InitLinklist(L); // 初始化
LNode *s= L; // s是待插入结点
printf("\n请输入链表各结点字符,以空格隔开(备注:需退出输入时,依次输入一次q,以空格隔开,最后再回车即可):\n");
scanf("%c%c",&c,&d);
while(c!='q'){
s = (LNode*)malloc(sizeof(LNode));
s->data = c;
s->next = L->next;
L->next = s;
// fflush(stdin);
scanf("%c%c",&c,&d);
}
return L;
}
4.尾插法建立一个单链表
Linklist List_TailInsert(Linklist &L){ // 正向建立单链表
char c,d; // c待插入的数据,d用于接收输入的空格并过滤
// InitLinklist(L); // 初始化,放在main函数中初始化
LNode *s,*r = L; // s是待插入结点,r是尾指针
printf("\n请输入链表各结点字符,以空格隔开(备注:需退出输入时,依次输入一次q,以空格隔开,最后再回车即可):\n");
scanf("%c%c",&c,&d);
while(c!='q'){
s = (LNode*)malloc(sizeof(LNode));
s->data = c;
r->next = s;
r = s;
/*一般情况下循环中循环中的scanf()只能使用一次,当本次循环结束之后下次语句执行到scanf()时,系统将自动跳过,
为什么呢?这要用键盘数据缓存区来解释,只有在此前加上fflush(stdin),表示清楚键盘缓存区内容*/
// fflush(stdin);
scanf("%c%c",&c,&d);
}
r->next = NULL;
return L;
}
5.打印链表,链表遍历
void printLink(Linklist L){
LNode *node = L->next;
printf("\n====以下为建立的单链表====\n");
while(node!= NULL){
printf("结点%c\t",node->data );
node = node->next;
}
}
6.查找第i-1个位置的结点
LNode *GetElemNode(Linklist L,int i) {
LNode *node = L->next;
int j=1;
while(node!= NULL and j<i-1){
j++;
printf("位置第%d个结点%c\t",j-1,node->data );
node = node->next;
}
printf("位置第%d个结点%c\t",j,node->data );
return node;
}
7.单链表删除结点
/*方法一:删除结点 *** 作是将单链表的第i个结点删除。先检查删除位置的合法性,后查找表中第i-1个结点,即被删除结点的前驱结点,再将其删除。算法时间复杂度为O(n).
方法二:其实,删除结点*s的 *** 作可用删除*s的后继结点 *** 作来实现,实质就是将其后继节点的值赋予其自身,然后删除后继节点,时间复杂度为O(1).*/
Linklist DeleteListNode(Linklist L,LNode *p){
LNode *q = p->next; //令q指向*p的后继节点
// 若q是最后一个结点
if (q->next==NULL){
printf("\n删除的结点为:%c\n",q->data);
free(q);
p->next=NULL;
}
else{
// q非最后一个结点
// 删除p结点,前驱结点为q
printf("\n删除的结点为:%c\n",p->data);
p->data = q->data; //和后继结点交换数据域
p->next = q->next; //将*q结点从链中“断开”
free(q); //释放后继结点的存储空间
}
return L;
}
8.完整代码
#include
#include
typedef char Elemtype; //将char重命名为Elemtype
// 定义单链表结构体
typedef struct LNode
{
Elemtype data; //定义数据域
struct LNode *next; //定义指针域
}LNode,*Linklist;
//1.初始化——创建一个带头结点的单链表
Linklist InitLinklist(Linklist &L){
L = (LNode*)malloc(sizeof(LNode)); // 分配一个头结点
if (L==NULL){
return NULL;
}
L->next = NULL;
return L;
}
//2.尾插法建立一个单链表
Linklist List_TailInsert(Linklist &L){ // 正向建立单链表
char c,d; // c待插入的数据,d用于接收输入的空格并过滤
// InitLinklist(L); // 初始化,放在main函数中初始化
LNode *s,*r = L; // s是待插入结点,r是尾指针
printf("\n请输入链表各结点字符,以空格隔开(备注:需退出输入时,依次输入一次q,以空格隔开,最后再回车即可):\n");
scanf("%c%c",&c,&d);
while(c!='q'){
s = (LNode*)malloc(sizeof(LNode));
s->data = c;
r->next = s;
r = s;
/*一般情况下循环中循环中的scanf()只能使用一次,当本次循环结束之后下次语句执行到scanf()时,系统将自动跳过,
为什么呢?这要用键盘数据缓存区来解释,只有在此前加上fflush(stdin),表示清楚键盘缓存区内容*/
// fflush(stdin);
scanf("%c%c",&c,&d);
}
r->next = NULL;
return L;
}
// 3.头插法建立一个单链表,倒序
Linklist List_HeadInsert(Linklist &L){
char c,d; // c待插入的数据,d用于接收输入的空格并过滤
// InitLinklist(L); // 初始化
LNode *s= L; // s是待插入结点
printf("\n请输入链表各结点字符,以空格隔开(备注:需退出输入时,依次输入一次q,以空格隔开,最后再回车即可):\n");
scanf("%c%c",&c,&d);
while(c!='q'){
s = (LNode*)malloc(sizeof(LNode));
s->data = c;
s->next = L->next;
L->next = s;
// fflush(stdin);
scanf("%c%c",&c,&d);
}
return L;
}
//4.打印链表,链表遍历
void printLink(Linklist L){
LNode *node = L->next;
printf("\n====以下为建立的单链表====\n");
while(node!= NULL){
printf("结点%c\t",node->data );
node = node->next;
}
}
// 查找第i-1个位置的结点
LNode *GetElemNode(Linklist L,int i) {
LNode *node = L->next;
int j=1;
while(node!= NULL and j<i-1){
j++;
printf("位置第%d个结点%c\t",j-1,node->data );
node = node->next;
}
printf("位置第%d个结点%c\t",j,node->data );
return node;
}
//5.单链表删除结点
/*方法一:删除结点 *** 作是将单链表的第i个结点删除。先检查删除位置的合法性,后查找表中第i-1个结点,即被删除结点的前驱结点,再将其删除。算法时间复杂度为O(n).
方法二:其实,删除结点*s的 *** 作可用删除*s的后继结点 *** 作来实现,实质就是将其后继节点的值赋予其自身,然后删除后继节点,时间复杂度为O(1).*/
Linklist DeleteListNode(Linklist L,LNode *p){
LNode *q = p->next; //令q指向*p的后继节点
// 若q是最后一个结点
if (q->next==NULL){
printf("\n删除的结点为:%c\n",q->data);
free(q);
p->next=NULL;
}
else{
// q非最后一个结点
// 删除p结点,前驱结点为q
printf("\n删除的结点为:%c\n",p->data);
p->data = q->data; //和后继结点交换数据域
p->next = q->next; //将*q结点从链中“断开”
free(q); //释放后继结点的存储空间
}
return L;
}
int main(){
system("color F5"); /* 其中color后面的0是背景色代号,A是前景色代号。*/
int i,j,k;
Linklist L;
L = InitLinklist(L);
printf("请输入数字1或者2,其中1=头插法,2=尾插法:\n");
scanf("%d",&i);
fflush(stdin);
if(i==1)
{ //头插法
L = List_HeadInsert(L);
}
else
{
L = List_TailInsert(L);
}
printLink(L);
printf("\n\n请输入数字3或者4,其中3=删除链表结点,4=退出程序:\n");
scanf("%d",&j);
fflush(stdin);
if(j==3)
{ // 删除链表结点
printf("\n请输入需要删除的结点位置(从1开始):\n");
scanf("%d",&k);
fflush(stdin);
LNode *p = GetElemNode(L,k);
L = DeleteListNode(L,p);
printLink(L);
return 0;
}
else{
return 0;
}
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)