创建一个链表头文件,其中包含的基本操作和定义,方便以后调用
/*
* 专业术语:
* 首节点:存放第一个有效数据的节点
* 尾节点:存放最后一个有效数据的节点
* 头结点
* 1、头结点的数据类型和【首节点的类型】是--摸一样的
* 2、头结点是【首节点】前面的那个节点。
* 3、头结点并【不存放有效数据】。
* 4、设置头结点的目的是为了方便对链表的操作。
* 头指针
* 存放头结点地址的指针变量
* 确定一个链表需要一个参数
* 头指针
*/
#include
#include //提供malloc()和free()
#include //开辟空间
#include //提供strcpy()等
typedef struct LNode{ //定义单链表结点类型
int data; //数据域,可以是别的各种数据类型,本文统一用int类型
struct LNode *next; //指针域
}LNode, *LinkList; //LNode等价于struct LNode; LinkList等价于truct LNode*
// 初始化单链表
LinkList Init_Table(LinkList L)
{
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
return L;
}
//头插法建立单链表
LinkList Head_Insert(LinkList L)
{
LNode* s; int x;int len;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
printf("头插法建立单链表,请输入链表长度:");
scanf("%d",&len);
for(int i = 0; i<len; i++)
{
printf("请输入要插入的整数:");
scanf("%d",&x);
s = (LinkList)malloc(sizeof(LNode)); //为s分配内存空间
s->data = x;
s->next = L->next;
L->next = s;
}
return L;
}
// 尾插法建立带表头单链表
LinkList Tail_Insert(LinkList L)
{
LNode* s, *r; // r为表尾指针。
int x,len;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
r = L;
printf("使用尾插法建立单链表,请输入链表长度:");
scanf("%d",&len);
for(int i = 0; i<len; i++)
{
printf("请输入要插入的整数:");
scanf("%d",&x);
s = (LinkList)malloc(sizeof(LNode)); //为s分配内存空间
s->data = x;
r->next = s; //开始链表为空,r指向表头, 现在需要将s节点链接到表头后面;
r = s; //让r指针指向表尾, 之后每次插入都可以在表尾插入了
}
r->next = NULL;
return L;
}
// 遍历链表
void Traverse_List(LinkList L)
{
LNode* p = L->next;
while(NULL != p)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
//带头结点的单链表, 根据索引,查找值
LNode* Get_Elem(LinkList L,int index)
{
int j = 1;
LNode* p = L->next; //第一个值。
if(index==0)
return L;
if(index<0)
return NULL;
while(p && j < index)
{
p = p->next; //进入循环,是从第二个值开始的,所以要j
j++;
}
return p;
}
//带有表头的单链表,按值查找表结点
LNode* Locate_Elem(LinkList L, int key)
{
LNode* p = L->next;
while(p->data!=key && p!=NULL)
p = p->next;
if(p!=NULL)
printf("找到了!");
else
printf("查找失败!");
return p; //找到后返回该节点指针,否则返回NULL.
}
//带表头,删除链表最后一个元素
LinkList Del_Tail_Elem(LinkList L)
{
LNode* p = L->next; //第一个值, p 最后指向链表最后一个值
LNode* q = L; //q指向表头, q 最后指向链表倒数第二个值
while(NULL!=p->next)
{
q = p; //如果后面还有元素,就把p的地址赋给q,然后让q指向后面的元素
p = p->next;
}
free(p); // 释放最后一个值的内存
q->next = NULL; //把倒数第二个值的指针域设置为空,就这样,最后一个值就删除完成了。
return L;
}
//带表头,删除链表第一个元素
LinkList Del_Head_Elem(LinkList L)
{
LNode* p = L->next; //第一个值,
LNode* q = L; //表头
q->next = p->next;
free(p);
return L;
}
//带表头,求表的长度
int Length(LinkList L)
{
int len;
LNode* p = L->next; //第一个值。
if(NULL==L->next)
len = 0;
while(p!=NULL)
{
len = len + 1;
p = p->next;
}
return len;
}
// 带表头,末尾插入一个元素。
LinkList Insert_Tail_Elem(LinkList L, int key)
{
LNode* p = L->next;
LNode* s;
while(NULL!=p->next)
p = p->next; // 循环直到p指向最后一个结点
s = (LinkList)malloc(sizeof(LNode)); // 为分配内存空间
s->data = key;
p->next = s;
s->next = NULL;
return L;
}
// 带表头,头插法入一个元素。
LinkList Insert_Head_Elem(LinkList L, int key)
{
LNode* s = NULL;
s = (LinkList)malloc(sizeof(LNode));
s->data = key;
s->next = L->next;
L->next = s;
return L;
}
给出两个排序的整数数组A和B,将B合并到A中作为一个排序的数组。注意:
if __name__ == '__main__':
list1 = [1, 3, 5, 7]
list2 = [2, 4, 6, 8]
list1 = list1+list2
list1.sort()
print(list1)
题目:给你两个代表两个非负数的链接列表。它们每位数字都是按照逆序的方式存储的,每个节点都包含一个数字。将这两个数字相加,并作为一个链表返回。
解析:因为逆序的方式进行存储:所以开始存储时采用头插法
LinkList Add(LinkList L1,LinkList L2){//两个表带首节点进行相加
LNode* p = NULL; // 指向最长的链表
LNode* q = NULL; // 指向最短的链表
int pro = 0; //表示进位
if(Length(L1)>=Length(L2))
{
p = L1->next;
q = L2->next;
}
else
{
p = L2->next;
q = L1->next;
}
while(q != NULL) //q指针指向得为最短的链表
{
int temp = p->data + q->data + pro;
if (temp >= 10)
{
pro = 1;
p->data = temp % 10;
}
else
{
pro = 0;
p->data = temp;
}
p = p->next;
q = q->next;
}
while(p != NULL)
{
int temp = p->data + pro;
if (temp >= 10)
{
pro = 1;
p->data = temp % 10;
}
else
{
pro = 0;
p->data = temp;
}
p = p->next;
}
if(Length(L1)>=Length(L2))
{
printf("最后的进位数为:%d\n",pro);
if(pro != 0)
L1 = Insert_Tail_Elem(L1, pro);
return L1;
}
else
{
printf("最后的进位数为:%d\n",pro);
if(pro != 0)
L2 = Insert_Tail_Elem(L2, pro);
return L2;
}
}
int main(void)
{
setvbuf(stdout,NULL,_IONBF,0);
LNode* Node = NULL;
LNode* Node2 = NULL;
LinkList L1 = Head_Insert(Node);
LinkList L2 = Head_Insert(Node2);
LinkList L3 = Add(L1, L2);
printf("两者相加的和为:");
Traverse_List(L3);
return 0;
}
输出
头插法建立单链表,请输入链表长度:2
请输入要插入的整数:9
请输入要插入的整数:9
9 9
头插法建立单链表,请输入链表长度:3
请输入要插入的整数:9
请输入要插入的整数:9
请输入要插入的整数:9
9 9 9
最后的进位数为:1
两者相加的和为:8 9 0 1
给出一个链接列表和一个值x,对其进行分区,使所有小于x的节点
排在大于等于x的节点
之前。
你应该保留两个分区中每个节点的原始相对顺序。例如,