链表
2026-08-24 10:41:45
发布于：广东
6阅读
0回复
0点赞
原始链表
#include<bits/stdc++.h>
using namespace std;
typedef struct List *link;
typedef struct List lnode;
struct List{
int data;
struct List *next;
};
// 清空链表
link clear(link head){
link p=head,q;
while(p!=NULL){
q=p->next;
delete(p);
p=q;
}
return NULL;
}
// 头插法创建链表，输入-1结束
link create(link head){
int x;
while(cin>>x&&x!=-1){
link p=new lnode;
p->data=x;
p->next=head;
head=p;
}
return head;
}
// 获取第i个元素，i从1开始，失败返回-1
int get(link head,int i){
int pos=1;
link p=head;
for(;p!=NULL&&pos<i;p=p->next){
pos++;
}
if(p==NULL) return -1;
return p->data;
}
// 按值查找，返回位置，找不到返回-1
int locate(link head,int num){
int ans_id=1;
link p=head;
for(;p!=NULL;p=p->next){
if(p->data == num){
return ans_id;
}
ans_id++;
}
return -1;
}
// 获取链表长度
int get_size(link head){
link p=head;
int len=0;
for(;p!=NULL;p=p->next){
len++;
}
return len;
}
// 在第i位置插入num，i从1开始；引用修改头结点
void insert(link &head,int i,int num){
if(i==1){
link s=new lnode;
s->data=num;
s->next=head;
head=s;
return;
}
int pos=1;
link p=head;
for(;p!=NULL&&pos<i-1;p=p->next){
pos++;
}
if(p == NULL)return;
link s=new lnode;
s->data=num;
s->next=p->next;
p->next=s;
}
// do while打印链表
void print(link head){
link p=head;
if(p==NULL){
cout<<"empty"<<endl;
return ;
}
do{
cout<<p->data<<" ";
p=p->next;
}while(p!=NULL);
cout<<endl;
}
// 删除第i个结点，引用head处理头删
void delete_num(link &head,int i){
link p=head,q;
if(i==1){
if(head==NULL){
return ;
}
q=head;
head=head->next;
delete q;
return;
}
int idx=1;
p=head;
while(p!=NULL&&idx<i-1){
p=p->next;
idx++;
}
if(p==NULL||p->next==NULL){
return ;
}
q=p->next;
p->next=q->next;
delete q;
}
int main(){
return 0;
}
数组模拟
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int val[MAXN];
int nxt[MAXN];
int head;
int tot;
inline void InitList()
{
head = 0;
tot = 0;
}
inline int NewNode(int data)
{
tot++;
val[tot] = data;
nxt[tot] = 0;
return tot;
}
void Create() //头插法构建链表,注意：头插会颠倒输入顺序
{
int newData;
while(cin >> newData)
{
if(newData == -1) //输入-1结束
return;
int np = NewNode(newData);
nxt[np] = head;
head = np;
}
}
void Display(){
int p = head;
if(p == 0){
cout << "链表为空\n";
return;
}
while(p != 0){
cout << val[p] << " ";
p = nxt[p];
}
cout << '\n';
}
int Locate(int x){
int p = head;
int n = 0;
while(p != 0 && val[p] != x){
p = nxt[p];
n++;
}
if(p == 0)
return -1;
return n + 1;
}
int Length(){
int len = 0;
int p = head;
while(p != 0){
len++;
p = nxt[p];
}
return len;
}
int Get(int i){
int j = 1;
int p = head;
while(j < i && p != 0){
p = nxt[p];
j++;
}
if(p != 0)
return val[p];
return -1;
}
void Insert(int x, int i){//第i个位置插入x；i非法则不执行操作
int np = NewNode(x);
if(i == 1){
nxt[np] = head;
head = np;
return;
}
int j = 1;
int p = head;
while(j < i - 1 && p != 0 && nxt[p] != 0){
p = nxt[p];
j++;
}
if(p != 0 && j == i - 1){
nxt[np] = nxt[p];
nxt[p] = np;
}
}
void Del(int i) { //删除逻辑第i个位置结点；i非法则不执行操作
if(head == 0)return;
if(i == 1){
head = nxt[head];
return;
}
int j = 1;
int p = head;
while(j < i - 1 && p != 0 && nxt[p] != 0){
p = nxt[p];
j++;
}
if(p != 0 && nxt[p] != 0 && j == i - 1){
int t = nxt[p];
nxt[p] = nxt[t];
}
}
inline void SetNull(){
head = 0;
tot = 0;
}
int main(){
InitList();
Create();
Display();
Insert(100, 2);
Display();
Del(2);
Display();
return 0;
}
这里空空如也
有帮助，赞一个