数据结构
AI-摘要
YouduAI GPT
AI初始化中...
介绍自己
生成本文简介
推荐相关文章
前往主页
前往tianli博客
顺序表的创建、插入、删除和输出
#include<bits/stdc++.h>
using namespace std;
#define MaxSize 10
typedef struct {
int data[MaxSize];
int length;
}SqlList;
void InitList(SqlList &L){
L.length = 0;
}
void InputList(SqlList &L){
int x; cin>>x;
int i = 0;
while(x != -99999){
L.data[i] = x;
i++; L.length++;
cin >> x;
}
}
void PrintList(SqlList &L){
for(int i = 0; i < L.length; i++){
cout << L.data[i] <<",\n"[i==L.length - 1];
}
}
bool ListInsert(SqlList &L, int i, int e){
if(i < 1 || i > L.length + 1) return false;
if(L.length >= MaxSize) return false;
for(int j = L.length; j >= i; j--) // 将第i个及之后的元素后移
L.data[j] = L.data[j-1];
L.data[i-1] = e;
L.length++;
return true;
}
bool ListDelete(SqlList &L, int i, int &e){
if(i < 1 || i > L.length + 1) return false;
e = L.data[i-1];
for(int j = i; j <= L.length; j++)
L.data[j-1] = L.data[j];
L.length--;
return true;
}
int main(){
SqlList L;
InitList(L);
InputList(L);
PrintList(L);
cout << "intput insert position and num: ";
int i, n; cin >> i >> n;
if(ListInsert(L, i, n)) { cout << "insert success!" << endl; PrintList(L); }
else cout << "insert failed!" << endl;
cout << "input delete position: "; cin >> i;
int delNum;
if(ListDelete(L, i, delNum))
{ cout << "delete success! the deleted num is " << delNum << endl; PrintList(L); }
else
cout << "delete failed!" << endl;
return 0;
}
/* test samples, enter -99999 to end.
11 22 44 55 66 88 -99999
*/单链表的创建、插入、删除和输出
#include<bits/stdc++.h>
using namespace std;
#define LEN sizeof(struct Student)
struct Student{
int num;
float score;
struct Student *next;
};
int n; // record the numbers of students
struct Student *InitList(){
struct Student *head, *p1, *p2; n = 0;
p1 = p2 = (struct Student*) malloc(LEN);
scanf("%d, %f", &p1->num, &p1->score);
head = NULL;
while(p1->num != 0){
n++;
if(n == 1) head = p1;
else p2->next = p1;
p2 = p1;
p1 = (struct Student*) malloc(LEN);
scanf("%d, %f", &p1->num, &p1->score);
}
p2->next = NULL;
return head;
}
void PrintList(struct Student *p){
printf("\nThese %d student records are: \n", n);
if(p != NULL){
do{
printf("%d %5.1f\n", p->num, p->score);
p = p -> next;
} while (p != NULL);
}
}
struct Student *ListInsert(struct Student *head, struct Student *stud){ // assuming the list is ordered
struct Student *p0, *p1, *p2;
p1 = head;
p0 = stud;
if(head == NULL){
head = p0; p0 ->next = NULL;
}else{
while((p0->num > p1->num) && (p1->next != NULL)){
p2 = p1; p1 = p1->next;
}
if(p0->num <= p1->num){
if(head == p1) head = p0;
else p2->next = p0;
p0 ->next = p1;
}else{
p1->next = p0;
p0->next=NULL;
}
}
n++;
return head;
}
struct Student *ListDelete(struct Student *head, int num){
Student *p1, *p2;
if(head == NULL){
cout << "list is empty can't be delted! " << endl;
return head;
}
p1 = head; p2 = NULL;
while(p1 != NULL && p1->num != num ){ // traverse
p2 = p1; p1 = p1->next;
}
if(p1 == NULL){
printf("can't search %d student", num);
return head;
}
if(p2 == NULL){
head = head->next; // The deleted node is the head node
cout << "delete sucess!" << endl;
}else{
p2->next = p1->next; // The deleted nodes are intermediate nodes or tail nodes
cout << "delete sucess!" << endl;
}
n--;
return head;
}
int main() {
struct Student *pt;
pt = InitList();
PrintList(pt);
Student s1;
s1.num = 1004; s1.score = 88.88; s1.next = NULL;
Student *pt2 = ListInsert(pt, &s1);
PrintList(pt2);
int num; cout << "\ninput num(delete): "; cin >> num;
Student *pt3 =ListDelete(pt2, num);
PrintList(pt3);
return 0;
}
/* test samples
1001, 88.88
1002, 77.77
1003, 66.66
1005, 99.99
0
*/两有序链表升降序合并(去重)、相交、相差
#include<bits/stdc++.h>
using namespace std;
typedef struct LNode{
int data;
struct LNode *next;
}LNode, *LinkList;
bool InitList(LinkList &L){
L = (LNode *)malloc(sizeof(LNode)); // 带头节点
if(L == NULL) return false;
L->next = NULL;
return true;
}
void InputList(LinkList &L){
int x; cin>>x;
LinkList tail = L;
while(x != -99999){ // 输入 -99999 结束输入
LNode *newNode = (LNode*)malloc(sizeof(LNode));
newNode->data = x; newNode->next = NULL;
tail->next = newNode;
tail = newNode;
cin >> x;
}
}
void PrintList(LinkList &L){
LinkList p = L->next;
while(p != NULL){
cout << p->data << ",\n"[p->next == NULL];
p = p->next;
}
}
LinkList p1, p2, p3, tmp;
void MergeList1(LinkList &L1, LinkList &L2, LinkList &L3){
// 升序合并并去重
p1 = L1->next; p2 = L2->next;
L3 = p3 = L1;
while(p1 && p2){
if(p1->data < p2->data){
p3->next = p1; p3 = p1; p1 = p1->next;
}else if(p2->data < p1->data){
p3->next = p2; p3 = p2; p2 = p2->next;
}else{
p3->next = p1; p3 = p1; p1 = p1->next;
tmp = p2->next; delete p2; p2 = tmp;
}
}
p3->next = p1?p1:p2;
delete L2;
}
void MergeList2(LinkList &L1, LinkList &L2, LinkList &L3){
// 降序合并
p1 = L1->next; p2 = L2->next;
L3 = L1;
L3->next = NULL;
while(p1 || p2){
if(!p1) { tmp = p2; p2 = p2->next; }
else if(!p2) { tmp = p1; p1 = p1->next; }
else if(p1->data <= p2->data) { tmp = p1; p1 = p1->next; }
else { tmp = p2; p2 = p2->next; }
tmp->next = L3->next; L3->next = tmp;
}
delete L2;
}
void MixList(LinkList &L1, LinkList &L2, LinkList &L3){
// 两链表相交
p1 = L1->next; p2 = L2->next;
L3 = p3 = L1;
while(p1 && p2){
if(p1->data == p2->data){
p3->next = p1; p3 = p1; p1 = p1->next;
tmp = p2; p2 = p2->next; delete tmp;
}else if(p1->data < p2->data){
tmp = p1; p1 = p1->next; delete tmp;
}else{
tmp = p2; p2 = p2->next; delete tmp;
}
}
while(p1) { tmp = p1; p1 = p1->next; delete tmp; }
while(p2) { tmp = p2; p2 = p2->next; delete tmp; }
p3->next = NULL;
delete L2;
}
void DiffList(LinkList &L1, LinkList &L2, int &n){
// 两链表相差
p1 = L1->next; p2 = L2->next;
p3 = L1;
while(p1 && p2){
if(p1->data < p2->data){
p3 = p1; p1 = p1->next; n++;
}else if(p1->data > p2->data){
p2 = p2->next;
}else{
p3->next = p1->next;
tmp = p1; p1 = p1->next; delete tmp;
}
}
}
int main(){
LinkList L1, L2, L3; InitList(L1); InitList(L2); InitList(L3);
InputList(L1); InputList(L2); // PrintList(L1); PrintList(L2); // 初始化并输入输出两个链表
MergeList1(L1, L2, L3);
cout << "两链表升序合并并去重: "; PrintList(L3);
LinkList L4, L5, L6; InitList(L4); InitList(L5); InitList(L6);
InputList(L4); InputList(L5); // PrintList(L4); PrintList(L5); // 初始化并输入输出两个链表
MergeList2(L4, L5, L6);
cout << "两链表降序合并: "; PrintList(L6);
LinkList L7, L8, L9; InitList(L7); InitList(L8); InitList(L9);
InputList(L7); InputList(L8);
MixList(L7, L8, L9);
cout << "两链表相交: "; PrintList(L9);
LinkList L10, L11; InitList(L10); InitList(L11);
InputList(L10); InputList(L11); int n = 0;
DiffList(L10, L11, n);
cout << "两链表相差: "; PrintList(L10);
cout << "元素个数位: " << n << endl;
return 0;
}
/* test samples
1 3 5 7 9 13 15 -99999
2 4 6 8 10 11 13 14 15 -99999
*/测试结果:
- 感谢你赐予我前进的力量
-
微信 
支付宝
赞赏者名单
因为你们的支持让我意识到写文章的价值🙏
阅读建议
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果
最近发布